結果

問題 No.1344 Typical Shortest Path Sum
コンテスト
ユーザー Omura Shunsuke
提出日時 2021-01-16 16:09:36
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 654 bytes
コンパイル時間 372 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 537,436 KB
最終ジャッジ日時 2024-11-27 19:17:59
合計ジャッジ時間 29,067 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 MLE * 1
other AC * 66 TLE * 8 MLE * 3
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

N,M=map(int,input().split())
L=[{}for i in range(N+1)]

for i in range(M):
    a,b,c=map(int,input().split())
    if b in L[a]:
        L[a][b] = min(L[a][b],c)
    else:
        L[a][b] = c
#print(L)

import heapq

for i in range(1,N+1):
    dist=[10**20 for i in range(N+1)]
    s=i
    Q=[(0,s)]
    heapq.heapify(Q)
    while len(Q)>0:
        d,p=heapq.heappop(Q)
        if dist[p]>d:
            dist[p]=d
            for k,v in L[p].items():
                if dist[k]>(v+d):
                    heapq.heappush(Q,(v+d,k))
    ans=0
    for i in dist[1:]:
        if i==10**20:
            continue
        else:
            ans+=i
    print(ans)
0