結果

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

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
testcase_28 WA -
testcase_29 WA -
testcase_30 WA -
testcase_31 WA -
testcase_32 WA -
testcase_33 WA -
testcase_34 WA -
権限があれば一括ダウンロードができます

ソースコード

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