結果
問題 |
No.1449 新プロランド
|
ユーザー |
|
提出日時 | 2023-06-17 20:31:51 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 574 ms / 2,000 ms |
コード長 | 1,238 bytes |
コンパイル時間 | 98 ms |
コンパイル使用メモリ | 12,800 KB |
実行使用メモリ | 39,936 KB |
最終ジャッジ日時 | 2024-12-24 02:12:15 |
合計ジャッジ時間 | 7,592 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
import sys from heapq import heappop, heappush input = sys.stdin.buffer.readline def dijkstra(N, G, s): INF = 10 ** 9 dist = [INF] * N que = [(0, s)] dist[s] = 0 while que: c, v = heappop(que) if dist[v] < c: continue for t, cost in G[v]: if dist[v] + cost < dist[t]: dist[t] = dist[v] + cost heappush(que, (dist[t], t)) return dist N, M = map(int, input().split()) MAX_TIME = 1000 G = [[] for _ in range(N * (MAX_TIME + 1))] def pair2int(num, time): return min(time, MAX_TIME) * N + num def add_edge(s_num, t_num, s_time, eat_time, length): t_time = s_time + eat_time if not t_time: return G[pair2int(s_num, s_time)].append((pair2int(t_num, t_time), eat_time + length // t_time)) edges = [] for _ in range(M): a, b, c = map(int, input().split()) a -= 1 b -= 1 edges.append((a, b, c)) T = tuple(map(int, input().split())) for a, b, c in edges: for time in range(MAX_TIME + 1): add_edge(a, b, time, T[a], c) add_edge(b, a, time, T[b], c) dist = dijkstra(len(G), G, pair2int(0, 0)) ans = min(dist[pair2int(N - 1, time)] for time in range(MAX_TIME + 1)) print(ans)