結果
問題 | No.1301 Strange Graph Shortest Path |
ユーザー | ygd. |
提出日時 | 2020-11-27 22:58:54 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,272 bytes |
コンパイル時間 | 284 ms |
コンパイル使用メモリ | 87,172 KB |
実行使用メモリ | 137,924 KB |
最終ジャッジ日時 | 2023-10-09 21:53:28 |
合計ジャッジ時間 | 23,208 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 69 ms
71,256 KB |
testcase_01 | AC | 66 ms
71,552 KB |
testcase_02 | WA | - |
testcase_03 | AC | 596 ms
116,300 KB |
testcase_04 | AC | 766 ms
135,360 KB |
testcase_05 | AC | 553 ms
116,592 KB |
testcase_06 | AC | 732 ms
130,376 KB |
testcase_07 | AC | 672 ms
126,060 KB |
testcase_08 | AC | 593 ms
115,832 KB |
testcase_09 | AC | 668 ms
128,652 KB |
testcase_10 | WA | - |
testcase_11 | AC | 704 ms
130,280 KB |
testcase_12 | AC | 705 ms
131,428 KB |
testcase_13 | AC | 591 ms
123,904 KB |
testcase_14 | AC | 637 ms
126,636 KB |
testcase_15 | AC | 583 ms
124,396 KB |
testcase_16 | AC | 714 ms
137,168 KB |
testcase_17 | AC | 620 ms
127,620 KB |
testcase_18 | AC | 580 ms
122,176 KB |
testcase_19 | AC | 668 ms
130,404 KB |
testcase_20 | AC | 669 ms
132,460 KB |
testcase_21 | AC | 627 ms
127,372 KB |
testcase_22 | AC | 651 ms
133,596 KB |
testcase_23 | AC | 632 ms
125,276 KB |
testcase_24 | AC | 650 ms
132,380 KB |
testcase_25 | AC | 717 ms
134,264 KB |
testcase_26 | AC | 663 ms
128,620 KB |
testcase_27 | AC | 684 ms
129,884 KB |
testcase_28 | AC | 564 ms
118,468 KB |
testcase_29 | WA | - |
testcase_30 | AC | 710 ms
133,036 KB |
testcase_31 | AC | 734 ms
133,008 KB |
testcase_32 | WA | - |
testcase_33 | WA | - |
testcase_34 | AC | 573 ms
125,960 KB |
ソースコード
from heapq import heapify, heappop, heappush N,M = map(int,input().split()); INF = float("inf") Graph = [[] for _ in range(N)] INPUT = [] for i in range(M): s,g,x,y = map(int,input().split()); INPUT.append((s,g,x,y)) s-=1;g-=1 Graph[s].append((x,g)) Graph[g].append((x,s)) def dijkstra_heap2(s,G): #S:start, V: node, E: Edge, G: Graph V = len(G) d = [INF for _ in range(V)] d[s] = 0 prev = [0]*V prev[s] = -1 PQ = [] heappush(PQ,(0,s)) while PQ: c,v = heappop(PQ) if d[v] < c: continue d[v] = c for cost,u in G[v]: if d[u] <= cost + d[v]: continue d[u] = cost + d[v] prev[u] = v heappush(PQ,(d[u], u)) return d, prev D,PREV = dijkstra_heap2(0,Graph) #print(D) ans = D[N-1] #print(PREV) now = N-1 Used = set() while now != 0: mae = now now = PREV[mae] Used.add((mae,now)) #print(Used) Graph.clear() New_Graph = [[] for _ in range(N)] for P in INPUT: a,b,x,y = P a-=1;b-=1 if (a,b) in Used or (b,a) in Used: New_Graph[a].append((y,b)) New_Graph[b].append((y,a)) else: New_Graph[a].append((x,b)) New_Graph[b].append((x,a)) #print(New_Graph) RD, RPREV = dijkstra_heap2(N-1,New_Graph) #print(RD) ans += RD[0] print(ans)