結果
問題 | No.2739 Time is money |
ユーザー | norioc |
提出日時 | 2024-04-22 02:12:09 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 790 bytes |
コンパイル時間 | 302 ms |
コンパイル使用メモリ | 82,456 KB |
実行使用メモリ | 195,760 KB |
最終ジャッジ日時 | 2024-04-22 02:12:27 |
合計ジャッジ時間 | 15,104 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 40 ms
54,016 KB |
testcase_01 | AC | 39 ms
53,888 KB |
testcase_02 | AC | 260 ms
117,520 KB |
testcase_03 | AC | 712 ms
150,508 KB |
testcase_04 | AC | 255 ms
117,056 KB |
testcase_05 | AC | 486 ms
125,936 KB |
testcase_06 | AC | 849 ms
154,288 KB |
testcase_07 | AC | 989 ms
179,372 KB |
testcase_08 | AC | 668 ms
164,480 KB |
testcase_09 | AC | 735 ms
166,452 KB |
testcase_10 | AC | 463 ms
155,968 KB |
testcase_11 | AC | 1,364 ms
195,760 KB |
testcase_12 | AC | 404 ms
181,516 KB |
testcase_13 | AC | 407 ms
181,780 KB |
testcase_14 | AC | 394 ms
168,376 KB |
testcase_15 | WA | - |
testcase_16 | AC | 311 ms
140,552 KB |
testcase_17 | AC | 1,376 ms
187,144 KB |
testcase_18 | AC | 1,398 ms
180,008 KB |
testcase_19 | AC | 996 ms
156,488 KB |
ソースコード
from collections import defaultdict from heapq import heappush, heappop N, M, X = map(int, input().split()) adj = defaultdict(list) for _ in range(M): u, v, C, T = map(int, input().split()) u -= 1 v -= 1 adj[u].append((v, C, T)) adj[v].append((u, C, T)) q = [(0, 0, 0)] # (time, money, 頂点) used = set() while q: time, money, v = heappop(q) if v == N-1: print(time) exit() if v in used: continue used.add(v) for to, c, t in adj[v]: if to in used: continue if money >= c: heappush(q, (time+t, money-c, to)) else: lack = c - money d = (lack + X - 1) // X m2 = money + X * d - c t2 = time + d + t heappush(q, (t2, m2, to)) print(-1)