結果
問題 | No.1 道のショートカット |
ユーザー |
![]() |
提出日時 | 2017-06-01 19:38:33 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 122 ms / 5,000 ms |
コード長 | 1,489 bytes |
コンパイル時間 | 141 ms |
コンパイル使用メモリ | 12,672 KB |
実行使用メモリ | 12,672 KB |
最終ジャッジ日時 | 2024-07-20 16:30:12 |
合計ジャッジ時間 | 3,279 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 40 |
ソースコード
# coding: utf-8 import array, bisect, collections, copy, heapq, itertools, math, random, re, string, sys, time sys.setrecursionlimit(10 ** 7) INF = 10 ** 20 MOD = 10 ** 9 + 7 def II(): return int(input()) def ILI(): return list(map(int, input().split())) def IAI(LINE): return [ILI() for __ in range(LINE)] def IDI(): return {key: value for key, value in ILI()} def read(): N = II() C = II() V = II() S = ILI() T = ILI() Y = ILI() M = ILI() return (N, C, V, S, T, Y, M) def solve(N, C, V, S, T, Y, M): edge = collections.defaultdict(list) for i in range(V): edge[S[i] - 1].append((T[i] - 1, Y[i], M[i])) dp = [[INF] * (C + 1) for _ in range(N)] dp[0][C] = 0 queue = list() heapq.heappush(queue, (0, C)) while len(queue) > 0: now_ver, now_cost = heapq.heappop(queue) now_time = dp[now_ver][now_cost] for next_ver, next_cost, next_time in edge[now_ver]: if (now_cost - next_cost) < 0: continue else: if dp[next_ver][now_cost - next_cost] > (now_time + next_time): dp[next_ver][now_cost - next_cost] = now_time + next_time heapq.heappush(queue, (next_ver, now_cost - next_cost)) ans = INF for m in dp[N - 1]: ans = min(ans, m) if ans == INF: ans = -1 return ans def main(): params = read() print(solve(*params)) if __name__ == "__main__": main()