AtCoder Beginner Contest 208 [ D - Shortest Path Queries 2 ] https://atcoder.jp/contests/abc208/tasks/abc208_d

abc208_d.py

'''
[問題]
https://atcoder.jp/contests/abc208/tasks/abc208_d

[解説]
https://blog.hamayanhamayan.com/entry/2021/07/05/013220
　はまやん氏の解説。
　へー、この問題の処理は、ワーシャルフロイドの処理そのものなのね。
　なるほどねー。

[結果]
PyPy3(7.3.0) AC 2827ms
Python(3.8.2) TLE   あら、ダメか
'''

import sys

sys.setrecursionlimit(10 ** 6)  # 再帰上限の引き上げ
input = sys.stdin.readline

INF = 2 ** 63 - 1

N, M = map(int, input().split())

dist = [[INF] * N for _ in range(N)]
for i in range(N):
    # 同じ地点なので距離0
    dist[i][i] = 0

for _ in range(M):
    A, B, C = map(int, input().split())
    dist[A-1][B-1] = C

ans = 0

for k in range(N):
    for s in range(N):
        for t in range(N):
            # s -> t に行くコストと、 k経由で s->k, k->t のルートで行くコストを比較する
            dist[s][t] = min(dist[s][t], dist[s][k] + dist[k][t])

            if dist[s][t] < INF:
                ans += dist[s][t]

print(ans)