結果
| 問題 | No.1069 電柱 / Pole (Hard) |
| ユーザー |
 matumoto
|
| 提出日時 | 2022-07-22 03:58:00 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 12,102 bytes |
| コンパイル時間 | 340 ms |
| コンパイル使用メモリ | 86,888 KB |
| 実行使用メモリ | 286,236 KB |
| 最終ジャッジ日時 | 2023-09-16 09:00:55 |
| 合計ジャッジ時間 | 6,315 ms |
|
ジャッジサーバーID （参考情報） |
judge11 / judge13 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 187 ms
83,408 KB |
| testcase_01 | AC | 204 ms
79,900 KB |
| testcase_02 | AC | 181 ms
78,968 KB |
| testcase_03 | AC | 177 ms
78,960 KB |
| testcase_04 | TLE | - |
| testcase_05 | -- | - |
| testcase_06 | -- | - |
| testcase_07 | -- | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
| testcase_27 | -- | - |
| testcase_28 | -- | - |
| testcase_29 | -- | - |
| testcase_30 | -- | - |
| testcase_31 | -- | - |
| testcase_32 | -- | - |
| testcase_33 | -- | - |
| testcase_34 | -- | - |
| testcase_35 | -- | - |
| testcase_36 | -- | - |
| testcase_37 | -- | - |
| testcase_38 | -- | - |
| testcase_39 | -- | - |
| testcase_40 | -- | - |
| testcase_41 | -- | - |
| testcase_42 | -- | - |
| testcase_43 | -- | - |
| testcase_44 | -- | - |
| testcase_45 | -- | - |
| testcase_46 | -- | - |
| testcase_47 | -- | - |
| testcase_48 | -- | - |
| testcase_49 | -- | - |
| testcase_50 | -- | - |
| testcase_51 | -- | - |
| testcase_52 | -- | - |
| testcase_53 | -- | - |
| testcase_54 | -- | - |
| testcase_55 | -- | - |
| testcase_56 | -- | - |
| testcase_57 | -- | - |
| testcase_58 | -- | - |
| testcase_59 | -- | - |
| testcase_60 | -- | - |
| testcase_61 | -- | - |
| testcase_62 | -- | - |
| testcase_63 | -- | - |
| testcase_64 | -- | - |
| testcase_65 | -- | - |
| testcase_66 | -- | - |
| testcase_67 | -- | - |
| testcase_68 | -- | - |
| testcase_69 | -- | - |
| testcase_70 | -- | - |
| testcase_71 | -- | - |
| testcase_72 | -- | - |
| testcase_73 | -- | - |
| testcase_74 | -- | - |
| testcase_75 | -- | - |
| testcase_76 | -- | - |
| testcase_77 | -- | - |
| testcase_78 | -- | - |
| testcase_79 | -- | - |
| testcase_80 | -- | - |
| testcase_81 | -- | - |
| testcase_82 | -- | - |
ソースコード
# verification-helper: PROBLEM https://yukicoder.me/problems/no/1069
import sys
from collections import defaultdict
import heapq
from typing import List
import copy
import math
# Pointクラス
# コンストラクタで(x,y)に代入可能(指定しなかったら(0,0)の地点)
class Point:
def __init__(self, x: float = 0, y: float = 0, idx: int = 0):
self.x = x
self.y = y
self.idx = idx
# otherがPoint型でないならNotImplementedエラーを返す(標準にある)
def __eq__(self, other) -> bool:
if not isinstance(other, Point):
return NotImplemented
is_same_x = utility.equals(self.x, other.x)
is_same_y = utility.equals(self.y, other.y)
return is_same_x and is_same_y
def __lt__(self, other) -> bool:
return (self.x < other.x) or (self.x == other.x and self.y < other.y)
# -self
def __neg__(self):
return Point(-self.x, -self.y)
# self + Point
def __add__(self, other):
if not isinstance(other, Point):
return NotImplemented
return Point(self.x + other.x, self.y + other.y)
# self - Point
def __sub__(self, other):
if not isinstance(other, Point):
return NotImplemented
return self + (-other)
# self * Point
def __mul__(self, other):
if not isinstance(other, Point):
return NotImplemented
return Point((self.x * other.x) + (self.y * other.y),
(self.x * other.y) + (self.y * other.x))
# self * int
# self * float
def __mul__(self, other):
if not (isinstance(other, int) or isinstance(other, float)):
return NotImplemented
return Point(self.x * other, self.y * other)
# set用のhash、重複した地点はないことを前提にidxを参照してます。
def __hash__(self):
return hash(self.idx)
# idxのセッター
def set_idx(self, idx):
self.idx = idx
# -pi<=a<=pi となる角度a[rad]を返す
def radian(p: Point) -> float:
return math.atan2(p.y, p.x)
# -180<=a<=180 となる角度a[deg]を返す
def degree(p: Point) -> float:
return math.degrees(math.atan2(p.y, p.x))
# x*x+y*yを返す(ノルム)
def norm(p: Point) -> float:
return p.x * p.x + p.y * p.y
# 絶対値|p|を返す
def abs(p: Point) -> float:
return math.sqrt(norm(p))
# pをradだけ(0,0)を中心に回転させる
def rotate(p: Point, rad: float) -> Point:
return Point(math.cos(rad) * p.x + math.sin(-rad) * p.y,
math.sin(rad) * p.x + math.cos(-rad) * p.y)
def distance_pp(p1: Point, p2: Point) -> float:
return abs(p1 - p2)
# 十分に小さい数
def eps() -> float:
return pow(10, -7)
# 相対誤差がeps()
def equals(a: float, b: float) -> bool:
return math.fabs(a - b) < eps()
# 符号を調べる
def sign(a: float) -> int:
if a > eps():
return +1
if a < -eps():
return -1
return 0
class Edge:
def __init__(self, from_idx: int = 0, to_idx: int = 0, cost: float = 0):
self.from_idx = from_idx
self.to_idx = to_idx
self.cost = cost
def __eq__(self, other) -> bool:
if not isinstance(other, Edge):
return NotImplemented
same1 = self.from_idx == other.from_idx
same2 = self.to_idx == other.to_idx
same3 = self.cost == other.cost
return same1 and same2 and same3
def __lt__(self, other) -> bool:
if not isinstance(other, Edge):
return NotImplemented
return self.cost < other.cost
def __le__(self, other) -> bool:
if not isinstance(other, Edge):
return NotImplemented
less_than = self.cost < other.cost
equal = equals(self.cost, other.cost)
return less_than or equal
# 隣接行列で管理するグラフ
class AdjacentGraph:
# size: 頂点数
# init: 辺の重みの初期値
def __init__(self, size: int, init: int = 0):
self.size = size
self.dists: List[List[int]] = [[init for _ in range(size)] for _ in range(size)]
self.edges: List[Edge] = []
def add_edge(self, edge: Edge):
self.edges.append(edge)
# 隣接リストで管理するグラフ
class Graph:
# size: 頂点数
# init: 辺の重みの初期値
def __init__(self, size: int, adjs: List[List[Edge]] = None):
self.size = size
if adjs == None:
self.adjs: List[List[Edge]] = [[] for _ in range(size)] # 隣接頂点
else:
self.adjs: List[List[Edge]] = copy.deepcopy(adjs)
self.edges: List[Edge] = []
def add_edge(self, edge: Edge):
self.edges.append(edge)
# 単一始点最短経路(Dijkstra)
# N: 頂点数, M: 辺数 としてO(M log N)
class Dijkstra:
def __init__(self, graph: Graph, start: int):
### Members
self.graph = copy.deepcopy(graph)
self.inf = 10**18
n = self.graph.size
# bs[i] := 頂点iへの最短経路の1つ前の頂点番号(befores)
self.bs = [-1 for _ in range(n)]
# ds[i] := 頂点iにたどり着く最短経路(distances)
self.ds = [self.inf for _ in range(n)]
#n = self.graph.size
for edge in self.graph.edges:
f = edge.from_idx
to = edge.to_idx
cost = edge.cost
self.graph.adjs[f].append(Edge(f, to, cost))
### build
self.ds[start] = 0
# priority_queue
pq: List[tuple[int,int]] = []
pq.append((self.ds[start], start))
while pq:
tmp: tuple[int,int] = heapq.heappop(pq)
cost = tmp[0]
v = tmp[1]
if self.ds[v] < cost:
continue
for e in self.graph.adjs[v]:
to = e.to_idx
if self.ds[to] > self.ds[v] + e.cost:
self.ds[to] = self.ds[v] + e.cost
self.bs[to] = v
heapq.heappush(pq, (self.ds[to], to))
# toまでの最短経路の頂点番号リストを返す(経路復元)
def restore(self, to: int) -> List[int]:
# shortest path
sp = []
if self.bs[to] == -1:
sp.append(to)
return sp
while to != -1:
sp.append(to)
to = self.bs[to]
sp.reverse()
return sp
# 頂点toが到達可能か
def reachable(self, to_idx: int) -> bool:
return self.ds[to_idx] <= self.inf // 2
class KthShortestPath:
def list_to_str(self, path: List[int]) -> str:
s = ''
for v in path:
s += str(v)
return s
def __init__(self, graph: Graph, start: int, goal: int, k: int):
# Members
self.inf = 10**18
self.dists: List[int] = []
self.shortest_paths: List[List[int]] = []
n = graph.size
g = copy.deepcopy(graph)
# i頂点を始点としたDijkstra O(NMlogN)
dijkstras: List[Dijkstra] = [None for _ in range(n)]
for i in range(n):
dijkstras[i] = Dijkstra(g, i)
pq: List[(int, List[int])] = []
prev_path: List[int] = []
d = Dijkstra(g, start) # 最初の最短経路を求める
first_cost = d.ds[goal]
first_path = d.restore(goal)
used_path: set[str] = set() # 使用済み経路を格納 used_path[k] = kth path
self.dists.append(first_cost)
self.shortest_paths.append(first_path)
prev_path = first_path
used_path.add(self.list_to_str(first_path))
# str -> Graph
self.graphs = defaultdict(lambda: g) # 経路ごとにグラフを持つ、初期値はグラフg
# 2番目〜K番目の最短経路を求めるO(K)
for _ in range(k):
# print("prev_path:", prev_path)
# print("dists:", self.dists)
# print("shortest_paths:", self.shortest_paths)
# (prev_path[i], prev_path[i+1]) の辺を消すO(N)
for i in range(len(prev_path)-1):
spur_node: List[int] = prev_path[i]
spur_root: List[int] = prev_path[:i]
str_path: str = self.list_to_str(prev_path[:i+1])
# O(M+N log N)
# ここでprev_path[i],prev_path[i+1]の辺を消したい
# spur_rootに含まれる頂点も消したい(すでに訪れた頂点なので)
edges = self.graphs[str_path].edges
new_graph = Graph(n)
used_vetex_set = set(spur_root) # O(N)
for j in range(len(edges)): # O(M)
edge = edges[j]
should_remove_edge = edge.from_idx == prev_path[i] and edge.to_idx == prev_path[i+1]
if should_remove_edge:
continue
should_remove_reversed_edge = edge.to_idx == prev_path[
i] and edge.from_idx == prev_path[i+1]
if should_remove_reversed_edge:
continue
# O(logN)
if edge.from_idx in used_vetex_set or edge.to_idx in used_vetex_set:
continue
new_graph.add_edge(edge)
self.graphs[str_path] = new_graph
# spur_nodeを始点としてDijkstra O(M log N)
spur_d = Dijkstra(self.graphs[str_path], spur_node)
path = spur_root + spur_d.restore(goal)
# costの計算 O(N)
cost = 0
for j in range(len(path)-1):
v = path[j]
next_v = path[j+1]
cost += dijkstras[v].ds[next_v]
# cost = d.ds[spur_node] + spur_d.ds[goal]
# 到達不可能
if spur_d.ds[goal] >= self.inf:
continue
# print('--------------------------------')
# print("i:", i, "spur_node:", spur_node, "spur_root:", spur_root, "path to goal:", spur_d.restore(
# goal), "prev_path:", prev_path, "prev_path[i]:", prev_path[i], "prev_path[i+1]:", prev_path[i+1], "cost:", cost)
# for e in self.graphs[str_path].edges:
# print('from:', e.from_idx, 'to:',
# e.to_idx, 'cost:', e.cost)
# print('--------------------------------')
if (cost >= self.inf):
continue
# 経路が使用済みか O(NlogN)
str_path = self.list_to_str(path)
if str_path in used_path:
continue
heapq.heappush(pq, (cost, path))
used_path.add(str_path)
if not pq:
break
cost, path = heapq.heappop(pq)
invalid = False
for dist in self.dists:
if cost < dist:
invalid = True
break
if invalid:
continue
self.dists.append(cost)
self.shortest_paths.append(path)
prev_path = path
def main():
N,M,K = map(int,input().split())
X,Y = map(int,input().split())
X -= 1 # to 0-indexed
Y -= 1 # to 0-indexed
points = [copy.deepcopy(Point()) for _ in range(N)]
for i in range(N):
p, q = map(int, input().split())
points[i] = Point(x=p, y=q)
graph = Graph(N)
for i in range(M):
P, Q = map(int, input().split())
P -= 1 # to 0-indexed
Q -= 1 # to 0-indexed
dist = distance_pp(points[P], points[Q])
graph.add_edge(Edge(P, Q, dist))
graph.add_edge(Edge(Q, P, dist))
ksp = KthShortestPath(graph, X, Y, K)
for i in range(K):
ans = -1
if i < len(ksp.dists):
ans = ksp.dists[i]
if ans >= ksp.inf:
ans = -1
print(f"{ans:.50f}")
if __name__ == "__main__":
main()