結果
問題 | No.2565 はじめてのおつかい |
ユーザー |
![]() |
提出日時 | 2023-12-02 16:04:00 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 438 ms / 2,000 ms |
コード長 | 1,435 bytes |
コンパイル時間 | 331 ms |
コンパイル使用メモリ | 81,972 KB |
実行使用メモリ | 99,784 KB |
最終ジャッジ日時 | 2024-09-26 19:46:49 |
合計ジャッジ時間 | 16,591 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 50 |
ソースコード
import heapq def dijkstra2(adjList, s, g): # Initialize the distance from the start node s to all other nodes as infinity distance = [float('inf')] * len(adjList) distance[s] = 0 # Initialize the priority queue with the start node queue = [(0, s)] # (distance, node) while queue: # Get the node with the smallest distance dist, node = heapq.heappop(queue) # If this node has already been processed, then ignore it if dist > distance[node]: continue # Update the distances to the neighboring nodes for neighbor, cost in adjList[node]: new_dist = dist + cost if new_dist < distance[neighbor]: distance[neighbor] = new_dist heapq.heappush(queue, (new_dist, neighbor)) # If the distance to the goal node g is infinity, it means there is no path. if distance[g] == float('inf'): return 1e10 else: return distance[g] N, M = map(int, input().split()) adj_list = [[] for _ in range(N)] for i in range(M): u, v = map(int, input().split()) u -= 1 v -= 1 adj_list[u].append((v, 1)) ans1 = dijkstra2(adj_list, 0, N-2) + dijkstra2(adj_list, N-2, N-1) + dijkstra2(adj_list, N-1, 0) ans2 = dijkstra2(adj_list, 0, N-1) + dijkstra2(adj_list, N-1, N-2) + dijkstra2(adj_list, N-2, 0) ans = min(ans1, ans2) if (ans >= 1e10): print(-1) else: print(ans)