結果
問題 | No.1480 Many Complete Graphs |
ユーザー | tamato |
提出日時 | 2021-04-16 20:52:42 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 369 ms / 2,000 ms |
コード長 | 1,293 bytes |
コンパイル時間 | 334 ms |
コンパイル使用メモリ | 82,432 KB |
実行使用メモリ | 105,728 KB |
最終ジャッジ日時 | 2024-07-03 04:11:31 |
合計ジャッジ時間 | 13,544 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 38 ms
52,736 KB |
testcase_01 | AC | 38 ms
53,120 KB |
testcase_02 | AC | 36 ms
53,376 KB |
testcase_03 | AC | 36 ms
53,120 KB |
testcase_04 | AC | 34 ms
53,120 KB |
testcase_05 | AC | 36 ms
52,992 KB |
testcase_06 | AC | 35 ms
52,736 KB |
testcase_07 | AC | 34 ms
52,736 KB |
testcase_08 | AC | 36 ms
53,248 KB |
testcase_09 | AC | 52 ms
66,432 KB |
testcase_10 | AC | 50 ms
65,280 KB |
testcase_11 | AC | 46 ms
60,672 KB |
testcase_12 | AC | 43 ms
61,312 KB |
testcase_13 | AC | 82 ms
83,584 KB |
testcase_14 | AC | 76 ms
82,060 KB |
testcase_15 | AC | 191 ms
89,016 KB |
testcase_16 | AC | 152 ms
85,024 KB |
testcase_17 | AC | 150 ms
84,352 KB |
testcase_18 | AC | 93 ms
80,896 KB |
testcase_19 | AC | 155 ms
84,512 KB |
testcase_20 | AC | 186 ms
87,092 KB |
testcase_21 | AC | 85 ms
82,304 KB |
testcase_22 | AC | 77 ms
81,016 KB |
testcase_23 | AC | 126 ms
92,940 KB |
testcase_24 | AC | 251 ms
92,192 KB |
testcase_25 | AC | 284 ms
98,304 KB |
testcase_26 | AC | 310 ms
98,860 KB |
testcase_27 | AC | 259 ms
92,804 KB |
testcase_28 | AC | 229 ms
105,728 KB |
testcase_29 | AC | 247 ms
105,472 KB |
testcase_30 | AC | 241 ms
105,156 KB |
testcase_31 | AC | 243 ms
104,192 KB |
testcase_32 | AC | 242 ms
105,468 KB |
testcase_33 | AC | 232 ms
105,096 KB |
testcase_34 | AC | 237 ms
105,492 KB |
testcase_35 | AC | 224 ms
105,668 KB |
testcase_36 | AC | 230 ms
105,180 KB |
testcase_37 | AC | 243 ms
104,208 KB |
testcase_38 | AC | 245 ms
105,344 KB |
testcase_39 | AC | 248 ms
104,576 KB |
testcase_40 | AC | 256 ms
105,344 KB |
testcase_41 | AC | 241 ms
105,312 KB |
testcase_42 | AC | 224 ms
104,960 KB |
testcase_43 | AC | 240 ms
105,600 KB |
testcase_44 | AC | 242 ms
105,388 KB |
testcase_45 | AC | 237 ms
105,264 KB |
testcase_46 | AC | 236 ms
104,320 KB |
testcase_47 | AC | 361 ms
103,432 KB |
testcase_48 | AC | 354 ms
103,060 KB |
testcase_49 | AC | 347 ms
103,188 KB |
testcase_50 | AC | 148 ms
98,048 KB |
testcase_51 | AC | 369 ms
103,376 KB |
testcase_52 | AC | 294 ms
103,172 KB |
testcase_53 | AC | 305 ms
103,168 KB |
testcase_54 | AC | 317 ms
103,552 KB |
testcase_55 | AC | 293 ms
103,860 KB |
testcase_56 | AC | 285 ms
103,368 KB |
testcase_57 | AC | 160 ms
101,900 KB |
testcase_58 | AC | 259 ms
105,620 KB |
evil_aftercontest.txt | AC | 390 ms
134,232 KB |
ソースコード
mod = 1000000007 eps = 10**-9 def main(): import sys input = sys.stdin.buffer.readline import heapq def dijkstra(adj, start): # adj: [[to, cost] * vertices], 0th index must be empty inf = 1 << 60 dist = [inf] * len(adj) dist[start] = 0 q = [] heapq.heappush(q, (0, start)) while q: min_dist, v_from = heapq.heappop(q) if min_dist > dist[v_from]: continue v_tos = adj[v_from] for v_to, cost in v_tos: if min_dist + cost < dist[v_to]: dist[v_to] = min_dist + cost heapq.heappush(q, (dist[v_to], v_to)) return dist N, M = map(int, input().split()) adj = [[] for _ in range(N+1 + M * 2)] for m in range(1, M+1): KCS = list(map(int, input().split())) k, c = KCS[:2] for s in KCS[2:]: adj[s].append((N + m, (s + 1) // 2)) adj[N + m].append((s, (s + 1) // 2 + c)) if s & 1: adj[s].append((N + m + M, s // 2)) adj[N + m + M].append((s, (s + 1) // 2 + c)) ans = dijkstra(adj, 1)[N] if ans < 1 << 60: print(ans) else: print(-1) if __name__ == '__main__': main()