結果
問題 | No.2565 はじめてのおつかい |
ユーザー |
|
提出日時 | 2023-12-02 16:09:35 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 491 ms / 2,000 ms |
コード長 | 1,227 bytes |
コンパイル時間 | 498 ms |
コンパイル使用メモリ | 82,048 KB |
実行使用メモリ | 94,592 KB |
最終ジャッジ日時 | 2024-09-26 19:54:17 |
合計ジャッジ時間 | 17,423 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 50 |
ソースコード
def INT():return int(input())def MI():return map(int, input().split())def LI():return list(map(int, input().split()))import heapqdef dijkstra(n, G, start=0):INF = 10**18dist = [INF] * ndist[start] = 0pq = []heapq.heappush(pq, (0, start))visited = [False] * nwhile pq:now = heapq.heappop(pq)[1]visited[now] = Truefor nxt, cost in G[now]:if dist[nxt] > dist[now] + cost and not visited[nxt]:dist[nxt] = dist[now] + costheapq.heappush(pq, (dist[now] + cost, nxt))return distN, M = MI()G = [[] for _ in range(N)]for _ in range(M):u, v = MI()u -= 1v -= 1G[u].append((v, 1))dist1 = dijkstra(N, G, 0) # from 0dist2 = dijkstra(N, G, N - 2) # from N - 2dist3 = dijkstra(N, G, N - 1) # from N - 1INF = 10**18if (dist1[N - 2] == INF or dist2[N - 1] == INF or dist3[0] == INF) or (dist1[N - 1] == INF or dist3[N - 2] == INF or dist2[0] == INF):print(-1)exit()cand1 = dist1[N - 2] + dist2[N - 1] + dist3[0]cand2 = dist1[N - 1] + dist3[N - 2] + dist2[0]ans = min(cand1, cand2)print(ans)