結果
問題 | No.2387 Yokan Factory |
ユーザー |
![]() |
提出日時 | 2023-07-21 21:51:59 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 2,951 ms / 5,000 ms |
コード長 | 2,340 bytes |
コンパイル時間 | 245 ms |
コンパイル使用メモリ | 82,432 KB |
実行使用メモリ | 220,032 KB |
最終ジャッジ日時 | 2024-09-21 23:22:09 |
合計ジャッジ時間 | 30,279 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 35 |
ソースコード
############################################################################################import bisect,collections,copy,heapq,itertools,math,string,sys,queue,time,randomfrom decimal import Decimaldef I(): return input()def IS(): return input().split()def II(): return int(input())def IIS(): return list(map(int,input().split()))def LIIS(): return list(map(int,input().split()))def make_divisors(n):lower_divisors , upper_divisors = [], []i = 1while i*i <= n:if n % i == 0:lower_divisors.append(i)if i != n // i:upper_divisors.append(n//i)i += 1return lower_divisors + upper_divisors[::-1]import mathdef prime_numbers(n):prime = [True for i in range(n+1)]prime[0] = Falseprime[1] = Falsesqrt_n = math.ceil(math.sqrt(n))for i in range(2, sqrt_n):if prime[i]:for j in range(2*i, n+1, i):prime[j] = Falsenumbers=[]for i in range(2,n+1):if prime[i]:numbers.append(i)return numbersdef factorization(n):arr = []temp = nfor i in range(2, int(-(-n**0.5//1))+1):if temp%i==0:cnt=0while temp%i==0:cnt+=1temp //= iarr.append([i, cnt])if temp!=1:arr.append([temp, 1])if arr==[]:arr.append([n, 1])return arrINF=1<<63MOD=998244353MOD2=10**9+7sys.setrecursionlimit(500005)alpha="ABCDEFGHIJKLMNOPQRSTUVWXYZ"def bit_count(x):return bin(x).count("1")def yesno(f):if f:print("Yes")else:print("No")####################################################l=-1r=10**10n,m,x=IIS()path=[[] for i in range(n)]for _ in range(m):u,v,a,b=IIS()path[u-1].append((v-1,a,b))path[v-1].append((u-1,a,b))def is_ok(val):q=[(0,0)]costs=[INF for i in range(n)]used=[0 for i in range(n)]costs[0]=0while q:c,v=heapq.heappop(q)if used[v]:continueused[v]=1for i,j,k in path[v]:if used[i] or val>k:continueif costs[i]>c+j:heapq.heappush(q,(c+j,i))costs[i]=c+jreturn costs[n-1]<=xwhile r-l>1:mid=(r+l)//2if is_ok(mid):l=midelse:r=midprint(l)