結果
問題 | No.1320 Two Type Min Cost Cycle |
ユーザー |
![]() |
提出日時 | 2020-12-09 18:15:03 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 868 ms / 2,000 ms |
コード長 | 1,308 bytes |
コンパイル時間 | 311 ms |
コンパイル使用メモリ | 81,848 KB |
実行使用メモリ | 80,824 KB |
最終ジャッジ日時 | 2024-09-20 01:21:21 |
合計ジャッジ時間 | 13,075 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 57 |
ソースコード
import sysimport bisectfrom heapq import *read = sys.stdin.buffer.readreadline = sys.stdin.buffer.readlinereadlines = sys.stdin.buffer.readlinesINF = 1 << 60T = int(readline())N, M = map(int, readline().split())G = []for e in range(M):u, v, c = map(int, readline().split())G.append((u, v, c))if T == 0:G.append((v, u, c))G.sort()frm = [g[0] for g in G]idx = [bisect.bisect_left(frm, v) for v in range(N + 2)]def dijkstra(S, T):dist = [INF] * (N + 1)dist[S] = 0q = [0 << 15 | S]while q:dv, v = divmod(heappop(q), 1 << 15)if dv > dist[v]:continueif v == T:return dvfor e in range(idx[v], idx[v + 1]):_, w, c = G[e]if (v, w) == (S, T):continuedw = dv + cif dist[w] > dw:dist[w] = dwheappush(q, dw << 15 | w)return INFdef main():done = set()ans = INFfor u, v, c in G:if (u, v) in done:continuedone.add((u, v))done.add((v, u))x = dijkstra(v, u) # v から u に、直接ではない行くx = x + c # cycle lengthans = min(ans, x)if ans == INF:ans = -1return ansprint(main())