結果
問題 | No.1320 Two Type Min Cost Cycle |
ユーザー | ningenMe |
提出日時 | 2020-12-13 04:24:29 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,026 ms / 2,000 ms |
コード長 | 1,273 bytes |
コンパイル時間 | 174 ms |
コンパイル使用メモリ | 81,716 KB |
実行使用メモリ | 81,032 KB |
最終ジャッジ日時 | 2023-10-20 05:42:47 |
合計ジャッジ時間 | 14,711 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 41 ms
53,512 KB |
testcase_01 | AC | 40 ms
53,512 KB |
testcase_02 | AC | 40 ms
53,512 KB |
testcase_03 | AC | 41 ms
53,512 KB |
testcase_04 | AC | 40 ms
53,512 KB |
testcase_05 | AC | 41 ms
53,512 KB |
testcase_06 | AC | 41 ms
53,512 KB |
testcase_07 | AC | 74 ms
75,800 KB |
testcase_08 | AC | 98 ms
76,192 KB |
testcase_09 | AC | 725 ms
80,100 KB |
testcase_10 | AC | 88 ms
76,312 KB |
testcase_11 | AC | 628 ms
79,472 KB |
testcase_12 | AC | 203 ms
77,404 KB |
testcase_13 | AC | 352 ms
78,320 KB |
testcase_14 | AC | 55 ms
68,056 KB |
testcase_15 | AC | 93 ms
76,472 KB |
testcase_16 | AC | 185 ms
76,936 KB |
testcase_17 | AC | 61 ms
72,704 KB |
testcase_18 | AC | 59 ms
72,160 KB |
testcase_19 | AC | 447 ms
78,716 KB |
testcase_20 | AC | 53 ms
63,244 KB |
testcase_21 | AC | 826 ms
80,468 KB |
testcase_22 | AC | 40 ms
53,512 KB |
testcase_23 | AC | 40 ms
53,512 KB |
testcase_24 | AC | 40 ms
53,512 KB |
testcase_25 | AC | 41 ms
53,512 KB |
testcase_26 | AC | 40 ms
53,512 KB |
testcase_27 | AC | 40 ms
53,512 KB |
testcase_28 | AC | 59 ms
72,160 KB |
testcase_29 | AC | 161 ms
76,752 KB |
testcase_30 | AC | 53 ms
64,272 KB |
testcase_31 | AC | 93 ms
75,740 KB |
testcase_32 | AC | 40 ms
53,512 KB |
testcase_33 | AC | 323 ms
77,628 KB |
testcase_34 | AC | 190 ms
76,800 KB |
testcase_35 | AC | 136 ms
76,376 KB |
testcase_36 | AC | 139 ms
76,660 KB |
testcase_37 | AC | 100 ms
76,100 KB |
testcase_38 | AC | 169 ms
76,764 KB |
testcase_39 | AC | 135 ms
76,560 KB |
testcase_40 | AC | 40 ms
53,512 KB |
testcase_41 | AC | 41 ms
53,512 KB |
testcase_42 | AC | 39 ms
53,512 KB |
testcase_43 | AC | 131 ms
76,928 KB |
testcase_44 | AC | 118 ms
76,864 KB |
testcase_45 | AC | 1,026 ms
80,284 KB |
testcase_46 | AC | 81 ms
75,656 KB |
testcase_47 | AC | 165 ms
76,864 KB |
testcase_48 | AC | 449 ms
78,664 KB |
testcase_49 | AC | 103 ms
76,108 KB |
testcase_50 | AC | 40 ms
53,512 KB |
testcase_51 | AC | 41 ms
53,512 KB |
testcase_52 | AC | 211 ms
76,848 KB |
testcase_53 | AC | 158 ms
76,576 KB |
testcase_54 | AC | 732 ms
80,512 KB |
testcase_55 | AC | 726 ms
80,472 KB |
testcase_56 | AC | 720 ms
80,492 KB |
testcase_57 | AC | 724 ms
80,856 KB |
testcase_58 | AC | 730 ms
80,872 KB |
testcase_59 | AC | 719 ms
81,032 KB |
ソースコード
#!/usr/bin/env python3 import sys import bisect from heapq import * read = sys.stdin.buffer.read readline = sys.stdin.buffer.readline readlines = sys.stdin.buffer.readlines INF = 1 << 60 T = 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(a, b): dist = [INF] * (N + 1) dist[a] = 0 q = [(0,a)] while q: dv, v = heappop(q) if dv > dist[v]: continue if v == b: return dv for e in range(idx[v], idx[v + 1]): _, w, c = G[e] if (v, w) == (a, b): continue dw = dv + c if dist[w] > dw: dist[w] = dw heappush(q, (dw,w)) return INF def main(): done = set() ans = INF for u, v, c in G: if (u, v) in done: continue done.add((u, v)) done.add((v, u)) x = dijkstra(v, u) # v から u に、直接ではない行く ans = min(ans, x + c) if ans == INF: ans = -1 return ans print(main())