結果
問題 |
No.1601 With Animals into Institute
|
ユーザー |
|
提出日時 | 2024-12-29 17:37:25 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,272 ms / 3,000 ms |
コード長 | 1,404 bytes |
コンパイル時間 | 780 ms |
コンパイル使用メモリ | 82,048 KB |
実行使用メモリ | 165,696 KB |
最終ジャッジ日時 | 2024-12-29 17:37:51 |
合計ジャッジ時間 | 20,859 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 36 |
ソースコード
## https://yukicoder.me/problems/no/1601 import heapq MAX_VALUE = 10 ** 18 def main(): N, M = map(int, input().split()) edges = [] for _ in range(M): a, b, c, x = map(int, input().split()) edges.append((a - 1, b - 1, c, x == 1)) # グラフ構築 next_nodes = [[] for _ in range(2 * N)] for a, b, c, x in edges: if x == 0: next_nodes[a].append((b, c)) next_nodes[b].append((a, c)) next_nodes[a + N].append((b + N, c)) next_nodes[b + N].append((a + N, c)) else: next_nodes[a + N].append((b, c)) next_nodes[b + N].append((a, c)) next_nodes[a + N].append((b + N, c)) next_nodes[b + N].append((a + N, c)) fix = [MAX_VALUE] * (2 * N) seen = [MAX_VALUE] * (2 * N) seen[2 * N - 1] = 0 queue = [] heapq.heappush(queue, (0, 2 * N - 1)) while len(queue) > 0: cost ,v = heapq.heappop(queue) if fix[v] < MAX_VALUE: continue fix[v] = cost for w, c in next_nodes[v]: if fix[w] < MAX_VALUE: continue new_cost = c + cost if seen[w] > new_cost: seen[w] = new_cost heapq.heappush(queue, (new_cost, w)) for i in range(N - 1): print(fix[i]) if __name__ == "__main__": main()