結果
問題 | 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 + 1new = N + 1adj = [[] 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 -> evenfor se in s_even:adj[se].append((new, se // 2))adj[new].append((se, c + se // 2))new += 1# even -> oddfor 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 -> evenfor 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 -> oddfor so in s_odd:adj[so].append((new, so // 2))adj[new].append((so, c + 1 + so // 2))new += 1INF = 10 ** 18pq = [(0, 1)]dp = [INF] * Vdp[1] = 0while pq:cost, v = heappop(pq)if cost > dp[v]:continuefor nv, dist in adj[v]:if dp[nv] > dp[v] + dist:dp[nv] = dp[v] + distheappush(pq, (dp[nv], nv))ans = dp[N]if ans == INF:ans = -1print(ans)