結果
問題 | No.2739 Time is money |
ユーザー | tassei903 |
提出日時 | 2024-04-17 03:22:02 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 739 bytes |
コンパイル時間 | 418 ms |
コンパイル使用メモリ | 82,308 KB |
実行使用メモリ | 195,776 KB |
最終ジャッジ日時 | 2024-04-17 03:22:36 |
合計ジャッジ時間 | 6,498 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 117 ms
88,724 KB |
testcase_01 | AC | 118 ms
88,696 KB |
testcase_02 | AC | 578 ms
133,616 KB |
testcase_03 | TLE | - |
testcase_04 | AC | 541 ms
133,060 KB |
testcase_05 | AC | 1,583 ms
148,284 KB |
testcase_06 | TLE | - |
testcase_07 | TLE | - |
testcase_08 | TLE | - |
testcase_09 | TLE | - |
testcase_10 | AC | 934 ms
163,476 KB |
testcase_11 | TLE | - |
testcase_12 | AC | 1,252 ms
183,104 KB |
testcase_13 | AC | 1,296 ms
182,536 KB |
testcase_14 | AC | 1,141 ms
181,732 KB |
testcase_15 | TLE | - |
testcase_16 | TLE | - |
testcase_17 | TLE | - |
testcase_18 | TLE | - |
ソースコード
from heapq import * from fractions import Fraction INF = 10**18 def dijkstra(g, s, n): dist = [INF]*n hq = [(0, s)] dist[s] = 0 while hq: d, v = heappop(hq) if dist[v]!=d: continue for to, c in g[v]: if dist[v] + c < dist[to]: dist[to] = dist[v] + c heappush(hq, (dist[to], to)) return dist from math import ceil n, m, x = list(map(int, input().split())) g = [[] for _ in range(n)] for i in range(m): u,v,c,t = list(map(int, input().split())) u -= 1 v -= 1 g[u].append((v,t+c / Fraction(x))) g[v].append((u,t+c / Fraction(x))) dist = dijkstra(g, 0, n) if dist[-1] == INF: print(-1) else: print(ceil(dist[-1]))