結果

問題 No.807 umg tours
コンテスト
ユーザー tpyneriver
提出日時 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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 4 WA * 7 MLE * 1 -- * 14
権限があれば一括ダウンロードができます

ソースコード

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