結果
問題 | No.807 umg tours |
ユーザー | neterukun |
提出日時 | 2019-06-10 06:48:53 |
言語 | Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0) |
結果 |
AC
|
実行時間 | 3,621 ms / 4,000 ms |
コード長 | 1,641 bytes |
コンパイル時間 | 76 ms |
コンパイル使用メモリ | 13,056 KB |
実行使用メモリ | 122,596 KB |
最終ジャッジ日時 | 2024-04-15 20:14:56 |
合計ジャッジ時間 | 34,724 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 35 ms
11,136 KB |
testcase_01 | AC | 31 ms
11,008 KB |
testcase_02 | AC | 32 ms
11,264 KB |
testcase_03 | AC | 32 ms
11,136 KB |
testcase_04 | AC | 31 ms
11,136 KB |
testcase_05 | AC | 31 ms
11,136 KB |
testcase_06 | AC | 33 ms
11,264 KB |
testcase_07 | AC | 32 ms
11,008 KB |
testcase_08 | AC | 32 ms
11,008 KB |
testcase_09 | AC | 30 ms
11,136 KB |
testcase_10 | AC | 30 ms
11,008 KB |
testcase_11 | AC | 2,237 ms
91,008 KB |
testcase_12 | AC | 1,819 ms
72,320 KB |
testcase_13 | AC | 2,667 ms
97,152 KB |
testcase_14 | AC | 1,020 ms
49,152 KB |
testcase_15 | AC | 736 ms
40,576 KB |
testcase_16 | AC | 2,819 ms
101,612 KB |
testcase_17 | AC | 3,615 ms
118,016 KB |
testcase_18 | AC | 3,569 ms
116,736 KB |
testcase_19 | AC | 3,421 ms
113,920 KB |
testcase_20 | AC | 1,536 ms
67,584 KB |
testcase_21 | AC | 1,550 ms
70,016 KB |
testcase_22 | AC | 550 ms
36,736 KB |
testcase_23 | AC | 420 ms
31,104 KB |
testcase_24 | AC | 1,664 ms
91,124 KB |
testcase_25 | AC | 3,621 ms
122,596 KB |
ソースコード
import sys import heapq imput = sys.stdin.readline def dijkstra(start, g): INF = float("inf") # distance[i][j] # := チケットを使ってないとき(i=0)、使ったとき(i=1)のj番目まで行くときの最短距離 distance = [[INF]*n for i in range(2)] distance[0][start] = 0 distance[1][start] = 0 cost = 0 #q = [(距離, 現在地, チケットを使っているかどうか)] q = [(0, start, 0)] while q: c, v, is_used = heapq.heappop(q) if is_used == 1: if distance[1][v] < c: continue for cost, t in g[v]: if distance[1][v] + cost < distance[1][t]: distance[1][t] = distance[1][v] + cost heapq.heappush(q, (distance[1][t], t, 1)) else: if distance[0][v] < c: continue for cost, t in g[v]: if distance[0][v] + cost < distance[0][t]: distance[0][t] = distance[0][v] + cost heapq.heappush(q, (distance[0][t], t, 0)) if distance[0][v] < distance[1][t]: distance[1][t] = distance[0][v] heapq.heappush(q, (distance[1][t], t, 1)) return distance n, m = map(int, input().split()) info = tuple(tuple(map(int, input().split())) for i in range(m)) graph = [[] for i in range(n)] for i in range(m): graph[info[i][0] - 1].append([info[i][2], info[i][1] - 1]) graph[info[i][1] - 1].append([info[i][2], info[i][0] - 1]) start = 0 ans = dijkstra(start, graph) for i in range(n): print(ans[0][i] + ans[1][i])