結果
問題 |
No.1344 Typical Shortest Path Sum
|
ユーザー |
![]() |
提出日時 | 2021-01-16 14:49:26 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 112 ms / 2,000 ms |
コード長 | 697 bytes |
コンパイル時間 | 270 ms |
コンパイル使用メモリ | 82,292 KB |
実行使用メモリ | 76,656 KB |
最終ジャッジ日時 | 2024-11-27 17:01:47 |
合計ジャッジ時間 | 7,028 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 77 |
ソースコード
import sys input = sys.stdin.readline def getlist(): return list(map(int, input().split())) def main(): n,m = getlist() INF = 10 ** 9 + 7 dist = [[float('inf')] * n for _ in range(n)] for i in range(n): dist[i][i] = 0 for _ in range(m): s,t,d = getlist() dist[s-1][t-1] = min(dist[s-1][t-1],d) for k in range(n): for i in range(n): for j in range(n): dist[i][j] = min(dist[i][j],dist[i][k] + dist[k][j]) for i in range(n): ans = 0 for j in range(n): if dist[i][j] != float('inf'): ans += dist[i][j] print(ans) if __name__ == '__main__': main()