結果

問題 No.2387 Yokan Factory
ユーザー えなじ~🔋▶️えなじ~🔋▶️
提出日時 2023-07-21 21:52:51
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,228 bytes
コンパイル時間 191 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 285,660 KB
最終ジャッジ日時 2024-09-21 23:23:36
合計ジャッジ時間 31,010 ms
ジャッジサーバーID
(参考情報)
judge1 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 17 TLE * 2 -- * 16
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

import heapq
N, M, X = map(int, input().split())
adj_list = []
for _ in range(M):
u,v,a,b = map(int, input().split())
adj_list.append([u,v,a,b])
small = -1
large = 10**9 + 1
while(large-small>1):
middle = (large + small)//2
#print(large, middle, small)
# middleX
adj = [[] for _ in range(N)]
for u,v,a,b in adj_list:
if middle <= b:
adj[u-1].append((v-1, a))
adj[v-1].append((u-1, a))
new_adj = []
for l in adj:
p = {}
for v,a in l:
if v in p.keys():
p[v] = min(p[v], a)
else:
p[v] = a
new_adj.append([(v,p[v]) for v in p.keys()])
adj = new_adj
times = [-1 for _ in range(N)]
q = [(0, 0)]
heapq.heapify(q)
#print(adj)
while(len(q)>0):
time, node = heapq.heappop(q)
if times[node]==-1:
times[node] = time
for v, d in adj[node]:
heapq.heappush(q, (time+d, v))
#print(times)
if times[N-1]==-1 or times[N-1]>X:
#
large = middle
else:
#
small = middle
print(small)
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0