結果
問題 | No.1320 Two Type Min Cost Cycle |
ユーザー |
|
提出日時 | 2020-12-17 00:32:41 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,317 ms / 2,000 ms |
コード長 | 1,432 bytes |
コンパイル時間 | 131 ms |
コンパイル使用メモリ | 82,208 KB |
実行使用メモリ | 200,304 KB |
最終ジャッジ日時 | 2024-09-20 05:35:24 |
合計ジャッジ時間 | 21,568 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 57 |
ソースコード
class Dijkstra():class Edge():def __init__(self, _to, _cost):self.to = _toself.cost = _costdef __init__(self, V):self.G = [[] for i in range(V)]self._E = 0self._V = V@propertydef E(self):return self._E@propertydef V(self):return self._Vdef add(self, _from, _to, _cost):self.G[_from].append(self.Edge(_to, _cost))self._E += 1def shortest_path(self, s):import heapqque = []d = [10**15] * self.Vd[s] = 0heapq.heappush(que, (0, s))while len(que) != 0:cost, v = heapq.heappop(que)if d[v] < cost: continuefor i in range(len(self.G[v])):e = self.G[v][i]if d[e.to] > d[v] + e.cost:d[e.to] = d[v] + e.costheapq.heappush(que, (d[e.to], e.to))return dT = int(input())N,M = map(int,input().split())edge = [tuple(map(int,input().split())) for i in range(M)]res = 10**15for i in range(M):tmp = Dijkstra(N)for j in range(M):u,v,w = edge[j]if i!=j:tmp.add(u-1,v-1,w)if not T:tmp.add(v-1,u-1,w)u,v,w = edge[i]d = tmp.shortest_path(v-1)[u-1]if d!=10**15:res = min(res,d+w)if res!=10**15:print(res)else:print(-1)