結果
| 問題 |
No.2387 Yokan Factory
|
| コンテスト | |
| ユーザー |
 shogo314
|
| 提出日時 | 2023-07-21 21:46:21 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 2,940 ms / 5,000 ms |
| コード長 | 5,292 bytes |
| コンパイル時間 | 350 ms |
| コンパイル使用メモリ | 82,048 KB |
| 実行使用メモリ | 287,520 KB |
| 最終ジャッジ日時 | 2024-09-21 23:13:50 |
| 合計ジャッジ時間 | 26,201 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 35 |
ソースコード
from typing import List, Tuple, Generic, TypeVar
from collections import deque
import heapq
Cost = TypeVar('Cost')
class Graph(Generic[Cost]):
"""
グラフの汎用クラス
"""
class Edge:
"""
グラフの辺を表すクラス
"""
def __init__(self, src: int, dst: int, cost: Cost, id: int):
self.src = src
self.dst = dst
self.cost = cost
self.id = id
def __int__(self):
return self.dst
def __init__(self, n: int):
"""
コンストラクタ
:param int n: 頂点数
:rtype: None
"""
self.n = n
self.m = 0
self.g = [[] for _ in range(n)]
def add_edge(self, u: int, v: int, w: Cost = 1):
"""
無向辺を追加する
:param int u: 始点
:param int v: 終点
:param int w: コスト 省略したら1
:rtype: None
"""
self.g[u].append(self.Edge(u, v, w, self.m))
self.g[v].append(self.Edge(v, u, w, self.m))
self.m += 1
def add_directed_edge(self, u: int, v: int, w: Cost = 1):
"""
有向辺を追加する
:param int u: 始点
:param int v: 終点
:param Cost w: コスト 省略したら1
:rtype: None
"""
self.g[u].append(self.Edge(u, v, w, self.m))
self.m += 1
def read(self, m: int, padding: int = -1, weighted: bool = False, directed: bool = False):
"""
辺の情報を標準入力から受け取って追加する
:param int m: 辺の数
:param int padding: 頂点番号を入力からいくつずらすか 省略したら-1
:param bool weighted: 辺の重みが入力されるか 省略したらfalseとなり、重み1で辺が追加される
:param bool directed: 有向グラフかどうか 省略したらfalse
:rtype: None
"""
for _ in range(m):
if weighted:
u, v, c = map(int, input().split())
else:
u, v = map(int, input().split())
c = 1
u += padding
v += padding
if directed:
self.add_directed_edge(u, v, c)
else:
self.add_edge(u, v, c)
def __getitem__(self, v: int) -> List[Edge]:
"""
ある頂点から出る辺を列挙する
:param int v: 頂点番号
:return: vから出る辺のリスト
:rtype: List[Edge]
"""
return self.g[v]
def shortest_path(self, s: int, weighted: bool = True, inf: Cost = -1) -> Tuple[List[Cost], List[Edge]]:
"""
ある頂点から各頂点への最短路
:param int s: 始点
:param int weighted: 1以外のコストの辺が存在するか 省略するとtrue
:param Cost inf: コストのminの単位元 未到達の頂点への距離はinfになる 省略すると2**31-1
:return: (各頂点への最短路長, 各頂点への最短路上の直前の辺)
:rtype: Tuple[List[Cost], List[Edge]]
"""
if weighted:
return self.__shortest_path_dijkstra(s, inf)
else:
return self.__shortest_path_bfs(s, inf)
def __shortest_path_bfs(self, s: int, inf: Cost) -> Tuple[List[int], List[Edge]]:
dist = [inf] * self.n
prev = [None] * self.n
que = deque()
dist[s] = 0
que.append(s)
while len(que) > 0:
u = que.popleft()
for e in self.g[u]:
if dist[e.dst] == inf:
dist[e.dst] = dist[e.src] + 1
prev[e.dst] = e
que.append(e.dst)
return dist, prev
def __shortest_path_dijkstra(self, s: int, inf: Cost) -> Tuple[List[Cost], List[Edge]]:
dist = [inf] * self.n
prev = [None] * self.n
que = []
dist[s] = 0
heapq.heappush(que, (0, s))
while len(que) > 0:
d, u = heapq.heappop(que)
if dist[u] < d:
continue
for e in self.g[u]:
if dist[e.dst] == inf or dist[e.dst] > dist[e.src] + e.cost:
dist[e.dst] = dist[e.src] + e.cost
prev[e.dst] = e
heapq.heappush(que, (dist[e.dst], e.dst))
return dist, prev
N, M, X = map(int, input().split())
uvab = []
l = []
for i in range(M):
u, v, a, b = map(int, input().split())
uvab.append((u-1, v-1, a, b))
l.append(b)
def query(Y):
g = Graph(N)
for u, v, a, b in uvab:
if b >= Y:
g.add_edge(u, v, a)
k = g.shortest_path(0, True)[0][-1]
if k == -1 or k > X:
return False
else:
return True
l = sorted(set(l))
if len(l) == 1:
if query(l[0]):
print(l[0])
else:
print(-1)
exit(0)
ans_max = len(l)-1
ans_min = 0
if not query(l[ans_min]):
print(-1)
exit(0)
if query(l[ans_max]):
print(l[ans_max])
exit(0)
while ans_max-ans_min > 1:
ans_mid = (ans_max+ans_min)//2
# print(l[ans_mid], query(l[ans_mid]))
if query(l[ans_mid]):
ans_min = ans_mid
else:
ans_max = ans_mid
print(l[ans_min])