結果
問題 | No.1480 Many Complete Graphs |
ユーザー |
![]() |
提出日時 | 2021-04-16 21:24:59 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 465 ms / 2,000 ms |
コード長 | 901 bytes |
コンパイル時間 | 351 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 103,016 KB |
最終ジャッジ日時 | 2024-07-03 04:13:23 |
合計ジャッジ時間 | 16,910 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 57 |
ソースコード
from heapq import *def dijkstra(g,start):n = len(g)INF = 1<<61dist = [INF]*(n) #startからの最短距離dist[start] = 0q = [(0,start)] #(そこまでの距離、点)while q:dv,v = heappop(q)if dist[v] < dv: continuefor to, cost in g[v]:if dv + cost < dist[to]:dist[to] = dv + costheappush(q, (dist[to], to))return distn,m = map(int,input().split())g = [[] for _ in range(1+n+2*m)]for i in range(m):k,c,*a = map(int,input().split())O = 2*i + n + 1E = 2*i + n + 2g[O].append((E,1))g[E].append((O,0))for ai in a:if ai%2:g[ai].append((O,ai//2+c))g[O].append((ai,ai//2+1))else:g[ai].append((E,ai//2+c))g[E].append((ai,ai//2))dist = dijkstra(g,1)print(dist[n] if dist[n] != 1<<61 else -1)