結果
問題 | No.1480 Many Complete Graphs |
ユーザー |
![]() |
提出日時 | 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 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 57 |
ソースコード
mod = 1000000007eps = 10**-9def main():import sysinput = sys.stdin.buffer.readlineimport heapqdef dijkstra(adj, start):# adj: [[to, cost] * vertices], 0th index must be emptyinf = 1 << 60dist = [inf] * len(adj)dist[start] = 0q = []heapq.heappush(q, (0, start))while q:min_dist, v_from = heapq.heappop(q)if min_dist > dist[v_from]:continuev_tos = adj[v_from]for v_to, cost in v_tos:if min_dist + cost < dist[v_to]:dist[v_to] = min_dist + costheapq.heappush(q, (dist[v_to], v_to))return distN, 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()