結果
問題 |
No.2387 Yokan Factory
|
ユーザー |
![]() |
提出日時 | 2023-07-21 21:59:18 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 2,567 ms / 5,000 ms |
コード長 | 902 bytes |
コンパイル時間 | 224 ms |
コンパイル使用メモリ | 82,048 KB |
実行使用メモリ | 276,884 KB |
最終ジャッジ日時 | 2024-09-21 23:31:43 |
合計ジャッジ時間 | 23,559 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 35 |
ソースコード
import sys input = sys.stdin.readline def dijkstra(G, s): from heapq import heappush, heappop INF = 10**18 dist = [INF] * len(G) dist[s] = 0 pq = [(0, s)] while pq: d, v = heappop(pq) if d > dist[v]: continue for u, weight in G[v]: nd = d + weight if dist[u] > nd: dist[u] = nd heappush(pq, (nd, u)) return dist N, M, X = map(int, input().split()) edges = [] for _ in range(M): u, v, a, b = map(int, input().split()) u -= 1 v -= 1 edges.append((u, v, a, b)) lb, ub = -1, 10**10 while ub - lb > 1: m = (lb + ub) // 2 G = [[]for _ in range(N)] for u, v, a, b in edges: if b >= m: G[u].append((v, a)) G[v].append((u, a)) dist = dijkstra(G, 0) if dist[N-1] <= X: lb = m else: ub = m print(lb)