結果
問題 | No.1480 Many Complete Graphs |
ユーザー |
|
提出日時 | 2021-04-16 21:53:42 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 612 ms / 2,000 ms |
コード長 | 1,174 bytes |
コンパイル時間 | 311 ms |
コンパイル使用メモリ | 81,792 KB |
実行使用メモリ | 116,556 KB |
最終ジャッジ日時 | 2024-07-03 04:15:28 |
合計ジャッジ時間 | 20,006 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 57 |
ソースコード
from heapq import * N, M = map(int, input().split()) V = N + 4 * M + 1 new = N + 1 adj = [[] for _ in range(V + 1)] for _ in range(M): k, c, *ss = map(int, input().split()) s_even = [s for s in ss if s % 2 == 0] s_odd = [s for s in ss if s % 2 == 1] # even -> even for se in s_even: adj[se].append((new, se // 2)) adj[new].append((se, c + se // 2)) new += 1 # even -> odd for se in s_even: adj[se].append((new, se // 2)) for so in s_odd: adj[new].append((so, c + 1 + so // 2)) new += 1 # odd -> even for so in s_odd: adj[so].append((new, so // 2)) for se in s_even: adj[new].append((se, c + 1 + se // 2)) new += 1 # odd -> odd for so in s_odd: adj[so].append((new, so // 2)) adj[new].append((so, c + 1 + so // 2)) new += 1 INF = 10 ** 18 pq = [(0, 1)] dp = [INF] * V dp[1] = 0 while pq: cost, v = heappop(pq) if cost > dp[v]: continue for nv, dist in adj[v]: if dp[nv] > dp[v] + dist: dp[nv] = dp[v] + dist heappush(pq, (dp[nv], nv)) ans = dp[N] if ans == INF: ans = -1 print(ans)