結果
問題 | No.1344 Typical Shortest Path Sum |
ユーザー |
![]() |
提出日時 | 2021-01-16 18:43:27 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 124 ms / 2,000 ms |
コード長 | 1,685 bytes |
コンパイル時間 | 157 ms |
コンパイル使用メモリ | 82,176 KB |
実行使用メモリ | 77,312 KB |
最終ジャッジ日時 | 2024-11-27 23:38:03 |
合計ジャッジ時間 | 6,937 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 77 |
ソースコード
class WarshallFloyd():def __init__(self, N):self.N = Nself.d = [[float("inf") for i in range(N)]for i in range(N)] # d[u][v] : 辺uvのコスト(存在しないときはinf)def add(self, u, v, c, directed=False):"""0-indexedであることに注意u = from, v = to, c = costdirected = Trueなら、有向グラフである"""if directed is False:self.d[u][v] = cself.d[v][u] = celse:if self.d[u][v]>c:self.d[u][v] = cdef WarshallFloyd_search(self):# これを d[i][j]: iからjへの最短距離 にする# 本来無向グラフでのみ全域木を考えるが、二重辺なら有向でも行けそう# d[i][i] < 0 なら、グラフは負のサイクルを持つfor k in range(self.N):for i in range(self.N):for j in range(self.N):self.d[i][j] = min(self.d[i][j], self.d[i][k] + self.d[k][j])hasNegativeCycle = Falsefor i in range(self.N):if self.d[i][i] < 0:hasNegativeCycle = Truebreakfor i in range(self.N):self.d[i][i] = 0return hasNegativeCycle, self.dN, M = map(int, input().split())ABT = [list(map(int, input().split())) for i in range(M)]graph = WarshallFloyd(N)for a, b, t in ABT:graph.add(a-1, b-1, t, True)hasNegativeCycle, D = graph.WarshallFloyd_search()for costs in D:ans = 0for cost in costs:if cost != float("inf"):ans+=costprint(ans)