結果

問題 No.1301 Strange Graph Shortest Path
ユーザー kit84kit84
提出日時 2020-11-28 00:11:43
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,986 bytes
コンパイル時間 146 ms
コンパイル使用メモリ 82,448 KB
実行使用メモリ 143,904 KB
最終ジャッジ日時 2024-07-26 21:20:18
合計ジャッジ時間 21,633 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 44 ms
56,448 KB
testcase_01 AC 50 ms
56,320 KB
testcase_02 WA -
testcase_03 AC 440 ms
124,020 KB
testcase_04 AC 695 ms
142,660 KB
testcase_05 AC 404 ms
125,824 KB
testcase_06 AC 655 ms
135,844 KB
testcase_07 AC 592 ms
131,788 KB
testcase_08 AC 487 ms
124,476 KB
testcase_09 AC 620 ms
133,248 KB
testcase_10 WA -
testcase_11 AC 651 ms
136,304 KB
testcase_12 AC 666 ms
138,068 KB
testcase_13 AC 710 ms
131,300 KB
testcase_14 AC 601 ms
131,664 KB
testcase_15 AC 582 ms
131,188 KB
testcase_16 AC 727 ms
142,740 KB
testcase_17 AC 567 ms
134,628 KB
testcase_18 AC 542 ms
129,152 KB
testcase_19 AC 698 ms
137,092 KB
testcase_20 AC 661 ms
137,728 KB
testcase_21 AC 598 ms
133,128 KB
testcase_22 AC 679 ms
139,468 KB
testcase_23 AC 598 ms
133,120 KB
testcase_24 AC 680 ms
138,240 KB
testcase_25 AC 698 ms
140,460 KB
testcase_26 AC 615 ms
133,624 KB
testcase_27 AC 649 ms
135,520 KB
testcase_28 AC 481 ms
126,740 KB
testcase_29 WA -
testcase_30 AC 702 ms
139,088 KB
testcase_31 AC 690 ms
140,652 KB
testcase_32 WA -
testcase_33 WA -
testcase_34 AC 631 ms
138,936 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
input = sys.stdin.readline
enum = enumerate
inf = 1001001001002002002
MOD = 998244353 #10**9 + 7

import collections
import random
from bisect import bisect_right as bs_r
from itertools import permutations
import heapq

def linput(ty=int, cvt=list):
	return cvt(map(ty,input().split()))

def vinput(rep=1, ty=int, cvt=list):
	return cvt(ty(input().rstrip()) for _ in range(rep))

def gcd(a: int, b: int):
	while b: a, b = b, a%b
	return a

def lcm(a: int, b: int):
	return a * b // gcd(a, b)

def dist(x1,y1,x2,y2):
	return abs(x1-x2)+abs(y1-y2)

vD = [chr(ord("a")+i) for i in range(26)]

def bye(res):
	sT = "No Yes".split()
	print(sT[res])
	#exit(0)
	
def csum(v):
	vr = [0,]
	s = 0
	for a in v:
		s = (s+a)	
		vr.append(s)
	return vr

def dijkstra(start, n, c_list):
    _vC = [inf,]*(n+1)
    _vC[start] = 0
    _vR = [0,]*(n+1) #set({})
    _vQ = [(0,start),]
    heapq.heapify(_vQ)
    while _vQ:
        _ci,_i = heapq.heappop(_vQ)
        if _vC[_i] < _ci:
            continue
        for _cj,_j,_m in c_list[_i]:
            if _vC[_j] > _vC[_i] + _cj:
                _vC[_j] = _vC[_i] + _cj
                #_vM |= {_m,}
                _vR[_j] = _i
                heapq.heappush(_vQ, (_vC[_j],_j))
    return _vC, _vR

def main():
	N,M = linput()
	mT = [linput(int,tuple) for _ in range(M)]
	
	res = 0
	
	# 1st graph
	mG = [[] for _ in range(N+1)]
	for m, (u,v,c,d) in enum(mT):
		mG[u].append( (c,v,m) )
		mG[v].append( (c,u,m) )
	
	# dijkstra 1
	vC, vR = dijkstra(1, N, mG)
	#print(vC, vR)###
	res += vC[N]	
	
	# find a path
	vM = set({})
	vQ = [N,]
	while vQ:
		v = vQ.pop()
		u = vR[v]
		for c,gv,m in mG[u]:
			if gv==v:
				vQ.append(u)
				vM |= {m,}
				break
	
	# 2nd graph
	mG = [[] for _ in range(N+1)]
	for m, (u,v,c,d) in enum(mT):
		cost = d if m in vM else c
		mG[u].append( (cost,v,m) )
		mG[v].append( (cost,u,m) )
	
	# dijkstra 2
	vC, vR = dijkstra(N, N, mG)	
	#print(vC)###
	res += vC[1]
	
	print(res)


	
if __name__ == "__main__":
	main()
0