結果

問題 No.1344 Typical Shortest Path Sum
ユーザー H20H20
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

class WarshallFloyd():
def __init__(self, N):
self.N = N
self.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 = cost
directed = True
"""
if directed is False:
self.d[u][v] = c
self.d[v][u] = c
else:
if self.d[u][v]>c:
self.d[u][v] = c
def WarshallFloyd_search(self):
# d[i][j]: ij
#
# 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 = False
for i in range(self.N):
if self.d[i][i] < 0:
hasNegativeCycle = True
break
for i in range(self.N):
self.d[i][i] = 0
return hasNegativeCycle, self.d
N, 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 = 0
for cost in costs:
if cost != float("inf"):
ans+=cost
print(ans)
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0