提出 #24525389

---

ソースコード 拡げる

import sys
from collections import defaultdict, deque

def main(f):
  N, M = list(map(int, f.readline().split()))
  dp = [[0]*(N+1) for _ in range(N+1)]
  for _ in range(1, M+1):
    a, b, c = list(map(int, f.readline().split()))
    dp[a][b] = c

  result = 0
  for k in range(1, N+1): # 都市 k の経由を許可する
    for x in range(1, N+1):
      if dp[x][k] == 0:
        continue
      for y in range(1, N+1):
        if dp[k][y] == 0:
          continue
        if x == y:
          continue

        if dp[x][y] == 0:
          dp[x][y] = dp[x][k] + dp[k][y]
        else:
          dp[x][y] = min(dp[x][y], dp[x][k] + dp[k][y])
    result += sum(map(sum, dp))
  print(result)

main(sys.stdin)

提出情報

ジャッジ結果