結果
問題 |
No.1480 Many Complete Graphs
|
ユーザー |
![]() |
提出日時 | 2025-03-31 17:46:25 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,463 bytes |
コンパイル時間 | 238 ms |
コンパイル使用メモリ | 82,736 KB |
実行使用メモリ | 112,160 KB |
最終ジャッジ日時 | 2025-03-31 17:47:01 |
合計ジャッジ時間 | 12,556 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 45 WA * 12 |
ソースコード
import sys import heapq def main(): input = sys.stdin.read().split() ptr = 0 N = int(input[ptr]); ptr += 1 M = int(input[ptr]); ptr += 1 adj = [[] for _ in range(N + 1)] for _ in range(M): k = int(input[ptr]); ptr += 1 c = int(input[ptr]); ptr += 1 s = list(map(int, input[ptr:ptr + k])) ptr += k s1 = s[0] s2 = s[1] # Add edge between s1 and s2 cost_s1_s2 = (s1 + s2 + 1) // 2 + c adj[s1].append((s2, cost_s1_s2)) adj[s2].append((s1, cost_s1_s2)) # Add edges from each node to s1 and s2 for node in s: cost_to_s1 = (node + s1 + 1) // 2 + c adj[node].append((s1, cost_to_s1)) adj[s1].append((node, cost_to_s1)) cost_to_s2 = (node + s2 + 1) // 2 + c adj[node].append((s2, cost_to_s2)) adj[s2].append((node, cost_to_s2)) # Dijkstra's algorithm INF = float('inf') dist = [INF] * (N + 1) dist[1] = 0 heap = [] heapq.heappush(heap, (0, 1)) while heap: current_dist, u = heapq.heappop(heap) if u == N: break if current_dist > dist[u]: continue for v, w in adj[u]: if dist[v] > current_dist + w: dist[v] = current_dist + w heapq.heappush(heap, (dist[v], v)) print(dist[N] if dist[N] != INF else -1) if __name__ == '__main__': main()