結果
問題 | No.2387 Yokan Factory |
ユーザー |
![]() |
提出日時 | 2023-07-21 21:42:36 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 2,290 ms / 5,000 ms |
コード長 | 773 bytes |
コンパイル時間 | 288 ms |
コンパイル使用メモリ | 82,048 KB |
実行使用メモリ | 185,064 KB |
最終ジャッジ日時 | 2024-09-21 23:08:31 |
合計ジャッジ時間 | 19,293 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 35 |
ソースコード
import sys input = sys.stdin.readline from heapq import heappush,heappop INF=1<<60 N,M,X=map(int,input().split()) UVAB=[list(map(int,input().split())) for _ in range(M)] edge = [[] for _ in range(N)] for u,v,a,b in UVAB: u-=1;v-=1 edge[u].append((v,a,b)) edge[v].append((u,a,b)) def check(B): time = [INF]*N time[0]=0 que = [(0,0)] while que: x,v = heappop(que) if time[v]<x:continue for to,a,b in edge[v]: if b<B:continue x2 = x+a if x2 >= time[to]:continue time[to]=x2 heappush(que, (x2,to)) if time[-1]<=X:return True return False ok,ng=-1,10**9+1 while ok+1<ng: m = ok+ng>>1 if check(m): ok=m else: ng=m print(ok)