結果
問題 | No.1 道のショートカット |
ユーザー |
![]() |
提出日時 | 2021-02-12 15:01:06 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 128 ms / 5,000 ms |
コード長 | 1,438 bytes |
コンパイル時間 | 148 ms |
コンパイル使用メモリ | 82,264 KB |
実行使用メモリ | 77,956 KB |
最終ジャッジ日時 | 2024-07-19 08:15:08 |
合計ジャッジ時間 | 4,106 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 40 |
ソースコード
# coding:UTF-8 import sys from heapq import heappush, heappop MOD = 10 ** 9 + 7 INF = float('inf') N = int(input()) # 数字 C = int(input()) # 数字 V = int(input()) # 数字 S = list(map(int, input().split())) # スペース区切り連続数字 T = list(map(int, input().split())) # スペース区切り連続数字 Y = list(map(int, input().split())) # スペース区切り連続数字 M = list(map(int, input().split())) # スペース区切り連続数字 # ダイクストラ O((E+N)logN) dist = [[] for _ in range(N)] # dist[n]: ノード n に隣接する(ノード, 重み)をリストで持つ for i in range(V): s = S[i] - 1 t = T[i] - 1 c = Y[i] d = M[i] dist[s].append((t, c, d)) # dist[t].append((s, c, d)) ns = 0 hq = [(0, C, 0)] # (distance, node) dist_min = [[INF] * (C + 1) for _ in range(N)] dist_min[ns][C] = 0 seen = [[False] * (C + 1) for _ in range(N)] while hq: d, c, v = heappop(hq) # ノードを pop する if seen[v][c]: continue seen[v][c] = True for to, cost, dis in dist[v]: # ノード v に隣接しているノードに対して if c - cost >= 0 and seen[to][c - cost] == False and d + dis < dist_min[to][c - cost]: dist_min[to][c - cost] = d + dis heappush(hq, (dist_min[to][c - cost], c - cost, to)) res = min(dist_min[N-1]) if res == INF: res = -1 print("{}".format(res))