結果
問題 | No.1601 With Animals into Institute |
ユーザー | 👑 H20 |
提出日時 | 2021-07-11 20:46:29 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 2,192 ms / 3,000 ms |
コード長 | 2,124 bytes |
コンパイル時間 | 743 ms |
コンパイル使用メモリ | 86,896 KB |
実行使用メモリ | 280,820 KB |
最終ジャッジ日時 | 2023-09-14 20:22:15 |
合計ジャッジ時間 | 32,502 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 91 ms
71,708 KB |
testcase_01 | AC | 90 ms
71,664 KB |
testcase_02 | AC | 92 ms
71,792 KB |
testcase_03 | AC | 219 ms
82,176 KB |
testcase_04 | AC | 211 ms
81,288 KB |
testcase_05 | AC | 207 ms
81,684 KB |
testcase_06 | AC | 1,945 ms
271,692 KB |
testcase_07 | AC | 1,975 ms
275,240 KB |
testcase_08 | AC | 2,040 ms
274,988 KB |
testcase_09 | AC | 2,107 ms
279,500 KB |
testcase_10 | AC | 2,192 ms
280,820 KB |
testcase_11 | AC | 2,078 ms
280,224 KB |
testcase_12 | AC | 2,088 ms
278,736 KB |
testcase_13 | AC | 2,042 ms
279,076 KB |
testcase_14 | AC | 2,033 ms
279,304 KB |
testcase_15 | AC | 2,146 ms
279,344 KB |
testcase_16 | AC | 2,000 ms
278,440 KB |
testcase_17 | AC | 2,035 ms
278,660 KB |
testcase_18 | AC | 224 ms
81,660 KB |
testcase_19 | AC | 220 ms
81,736 KB |
testcase_20 | AC | 220 ms
81,716 KB |
testcase_21 | AC | 223 ms
81,772 KB |
testcase_22 | AC | 218 ms
81,864 KB |
testcase_23 | AC | 214 ms
82,060 KB |
testcase_24 | AC | 216 ms
81,612 KB |
testcase_25 | AC | 223 ms
82,244 KB |
testcase_26 | AC | 224 ms
82,060 KB |
testcase_27 | AC | 88 ms
71,540 KB |
testcase_28 | AC | 90 ms
71,836 KB |
testcase_29 | AC | 90 ms
71,612 KB |
testcase_30 | AC | 92 ms
71,704 KB |
testcase_31 | AC | 91 ms
71,496 KB |
testcase_32 | AC | 91 ms
71,680 KB |
testcase_33 | AC | 90 ms
71,664 KB |
testcase_34 | AC | 90 ms
71,692 KB |
testcase_35 | AC | 90 ms
71,676 KB |
testcase_36 | AC | 89 ms
71,648 KB |
testcase_37 | AC | 87 ms
71,440 KB |
testcase_38 | AC | 88 ms
71,676 KB |
ソースコード
import collections import heapq class Dijkstra(): def __init__(self): self.e = collections.defaultdict(list) def add(self, u, v, d, directed=False): """ #0-indexedでなくてもよいことに注意 #u = from, v = to, d = cost #directed = Trueなら、有向グラフである """ if directed is False: self.e[u].append([v, d]) self.e[v].append([u, d]) else: self.e[u].append([v, d]) def delete(self, u, v): self.e[u] = [_ for _ in self.e[u] if _[0] != v] self.e[v] = [_ for _ in self.e[v] if _[0] != u] def Dijkstra_search(self, s): """ #0-indexedでなくてもよいことに注意 #:param s: 始点 #:return: 始点から各点までの最短経路と最短経路を求めるのに必要なprev """ d = collections.defaultdict(lambda: float('inf')) prev = collections.defaultdict(lambda: None) d[s] = 0 q = [] heapq.heappush(q, (0, s)) v = collections.defaultdict(bool) while len(q): k, u = heapq.heappop(q) if v[u]: continue v[u] = True for uv, ud in self.e[u]: if v[uv]: continue vd = k + ud if d[uv] > vd: d[uv] = vd prev[uv] = u heapq.heappush(q, (vd, uv)) return d, prev def getDijkstraShortestPath(self, start, goal): _, prev = self.Dijkstra_search(start) shortestPath = [] node = goal while node is not None: shortestPath.append(node) node = prev[node] return shortestPath[::-1] N, M = map(int, input().split()) ABCX = [list(map(int, input().split())) for i in range(M)] graph = Dijkstra() for a,b,c,x in ABCX: graph.add(a,b,c) graph.add(-a,-b,c) if x>0: graph.add(a,-b,c) graph.add(-a,b,c) result,_ = graph.Dijkstra_search(-N) for i in range(1,N): print(result[i])