結果
問題 | No.1480 Many Complete Graphs |
ユーザー |
|
提出日時 | 2022-07-23 11:58:32 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 401 ms / 2,000 ms |
コード長 | 870 bytes |
コンパイル時間 | 537 ms |
コンパイル使用メモリ | 82,432 KB |
実行使用メモリ | 103,560 KB |
最終ジャッジ日時 | 2024-07-04 23:29:23 |
合計ジャッジ時間 | 15,687 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 57 |
ソースコード
import sys from heapq import heappop, heappush input = sys.stdin.buffer.readline N, M = map(int, input().split()) SIZE = N + 2 * M G = [[] for _ in range(SIZE)] def add_undirected_edge(u, v, c): G[u].append((v, c)) G[v].append((u, c)) INF = 10 ** 18 def dijkstra(N, G, s): dist = [INF] * N que = [(0, s)] dist[s] = 0 while que: c, v = heappop(que) if dist[v] < c: continue for t, cost in G[v]: if dist[v] + cost < dist[t]: dist[t] = dist[v] + cost heappush(que, (dist[t], t)) return dist for m in range(N, SIZE, 2): K, C, *S = map(int, input().split()) add_undirected_edge(m, m + 1, 1) for s in S: t = m + s % 2 add_undirected_edge(s - 1, t, C + s) dist = dijkstra(SIZE, G, 0)[N - 1] print(-1 if dist == INF else dist // 2)