結果
問題 | No.2569 はじめてのおつかいHard |
ユーザー |
👑 |
提出日時 | 2023-11-14 00:40:05 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 717 ms / 2,000 ms |
コード長 | 1,168 bytes |
コンパイル時間 | 337 ms |
コンパイル使用メモリ | 82,432 KB |
実行使用メモリ | 120,820 KB |
最終ジャッジ日時 | 2024-09-26 03:27:38 |
合計ジャッジ時間 | 5,643 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 10 |
ソースコード
from collections import dequefrom heapq import heappush, heappopINF = 1 << 60N, M = map(int, input().split())graph = [[] for _ in range(N)]graph_rev = [[] for _ in range(N)]for _ in range(M):u, v, t = map(int, input().split())u -= 1; v -= 1graph[u].append((t, v))graph_rev[v].append((t, u))def dijkstra(start, G):costs = [INF]*Ncosts[start] = 0pq = []heappush(pq, (0, start))while pq:now_t, now_v = heappop(pq)if costs[now_v] < now_t:continuefor next_t, next_v in G[now_v]:if costs[next_v] > costs[now_v] + next_t:costs[next_v] = costs[now_v] + next_theappush(pq, (now_t + next_t, next_v))return costsdi = {N-2: dijkstra(N-2, graph),N-1: dijkstra(N-1, graph)}di_rev = {N-2: dijkstra(N-2, graph_rev),N-1: dijkstra(N-1, graph_rev)}for i in range(N-2):ans_1 = di_rev[N-2][i] + di[N-2][N-1] + di[N-1][i]ans_2 = di_rev[N-1][i] + di[N-1][N-2] + di[N-2][i]ans = min(ans_1, ans_2)if ans < INF:print(ans)else:print(-1)