結果
問題 | No.2739 Time is money |
ユーザー | Theta |
提出日時 | 2024-04-23 17:44:08 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,547 ms / 2,000 ms |
コード長 | 1,095 bytes |
コンパイル時間 | 592 ms |
コンパイル使用メモリ | 82,172 KB |
実行使用メモリ | 159,540 KB |
最終ジャッジ日時 | 2024-04-23 17:44:30 |
合計ジャッジ時間 | 21,308 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 43 ms
52,608 KB |
testcase_01 | AC | 40 ms
52,480 KB |
testcase_02 | AC | 352 ms
113,104 KB |
testcase_03 | AC | 1,329 ms
137,928 KB |
testcase_04 | AC | 343 ms
112,000 KB |
testcase_05 | AC | 940 ms
117,400 KB |
testcase_06 | AC | 1,162 ms
120,696 KB |
testcase_07 | AC | 1,377 ms
158,076 KB |
testcase_08 | AC | 1,458 ms
159,540 KB |
testcase_09 | AC | 1,547 ms
158,804 KB |
testcase_10 | AC | 587 ms
138,020 KB |
testcase_11 | AC | 1,513 ms
159,156 KB |
testcase_12 | AC | 563 ms
146,688 KB |
testcase_13 | AC | 541 ms
146,572 KB |
testcase_14 | AC | 531 ms
145,280 KB |
testcase_15 | AC | 811 ms
149,440 KB |
testcase_16 | AC | 903 ms
135,936 KB |
testcase_17 | AC | 1,389 ms
155,976 KB |
testcase_18 | AC | 1,370 ms
155,564 KB |
testcase_19 | AC | 1,039 ms
147,192 KB |
ソースコード
from heapq import heappop, heappush from math import inf, isinf import sys def printe(*args, end="\n", **kwargs): print(*args, end=end, file=sys.stderr, **kwargs) def main(): N, M, X = map(int, input().split()) graph = [{} for _ in range(N)] for _ in range(M): u, v, C, T = map(int, input().split()) graph[u - 1][v - 1] = (C + T * X, T) graph[v - 1][u - 1] = (C + T * X, T) distance = [(inf, inf)] * N distance[0] = (0, 0) queue = [(0, 0, 0)] while queue: c_total, c_t, c_n = heappop(queue) if distance[c_n][0] < c_total: continue for n_n, (n_total, n_t) in graph[c_n].items(): if distance[n_n][0] > c_total + n_total: distance[n_n] = (c_total + n_total, c_t + n_t) heappush(queue, (c_total + n_total, c_t + n_t, n_n)) if isinf(distance[N - 1][0]): print(-1) else: print(distance[N - 1][1] + (distance[N - 1] [0] - distance[N - 1][1] * X + X - 1) // X) if __name__ == "__main__": main()