結果

問題 No.807 umg tours
ユーザー tpynerivertpyneriver
提出日時 2019-03-22 22:27:50
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,360 bytes
コンパイル時間 283 ms
コンパイル使用メモリ 82,648 KB
実行使用メモリ 669,116 KB
最終ジャッジ日時 2024-09-19 05:57:45
合計ジャッジ時間 7,016 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 AC 67 ms
72,480 KB
testcase_07 WA -
testcase_08 AC 39 ms
54,528 KB
testcase_09 AC 39 ms
54,912 KB
testcase_10 AC 41 ms
55,040 KB
testcase_11 MLE -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

import heapq
from collections import defaultdict
def dijkstra(vnum, vs, edge):
    dist = [10**20]*vnum
    dist[vs] = 0 
    remain = set(range(vnum))
    Q = []
    heapq.heappush(Q,(0,vs))
    while Q:
        c, vn = heapq.heappop(Q)
        if vn not in remain :
            continue
        remain.remove(vn)
        for j in remain:
            if dist[vn] + edge[vn][j] < dist[j]:
                dist[j] = dist[vn] + edge[vn][j] 
                heapq.heappush(Q,(dist[j],j)) 
        if not remain:
            break
    return dist
def dijkstra1(vnum, vs, edge, dist0):
    dist = [10**20]*vnum
    dist[vs] = 0 
    remain = set(range(vnum))
    Q = []
    heapq.heappush(Q,(0,vs))
    while Q:
        c, vn = heapq.heappop(Q)
        if vn not in remain :
            continue
        remain.remove(vn)
        for j in remain:
            if dist[vn] + edge[vn][j] < dist[j]:
                dist[j] = min(dist[vn] + edge[vn][j], dist0[vn])
                heapq.heappush(Q,(dist[j],j)) 
        if not remain:
            break
    return dist
N, M = map(int, input().split())
Edge = [defaultdict(lambda: 10**20) for _ in range(N)]
for _ in range(M):
    a, b, c = map(int, input().split())
    Edge[a-1][b-1] = c
    Edge[b-1][a-1] = c
D = dijkstra(N, 0, Edge)
D1 = dijkstra1(N, 0, Edge, D)
print('\n'.join([str(i+j) for i, j in zip(D, D1)]))
0