結果
問題 |
No.1565 Union
|
ユーザー |
![]() |
提出日時 | 2023-06-18 18:30:37 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 733 ms / 2,000 ms |
コード長 | 1,068 bytes |
コンパイル時間 | 397 ms |
コンパイル使用メモリ | 82,324 KB |
実行使用メモリ | 114,980 KB |
最終ジャッジ日時 | 2024-12-20 18:26:59 |
合計ジャッジ時間 | 10,781 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 27 |
ソースコード
# 問題読み間違えていた、頂点1とNを連結したい # それならダイクストラだろう N, M = map(int, input().split()) edges = [[] for i in range(N+1)] for i in range(M): a, b = map(int, input().split()) edges[a].append((b, 1)) edges[b].append((a, 1)) from heapq import heappush, heappop INF = 10 ** 18 def dijkstra(s, n, connect): #(始点, ノード数) distance = [INF] * n que = [(0, s)] #(distance, node) distance[s] = 0 confirmed = [False] * n # ノードが確定済みかどうか while que: w,v = heappop(que) if distance[v]<w: continue confirmed[v] = True for to, cost in connect[v]: # ノード v に隣接しているノードに対して if confirmed[to] == False and distance[v] + cost < distance[to]: distance[to] = distance[v] + cost heappush(que, (distance[to], to)) return distance distance = dijkstra(1, N+1, edges) #print(distance) ans = distance[N] if ans == INF: print(-1) else: print(ans)