# verification-helper: PROBLEM https://yukicoder.me/problems/no/1069 import sys import heapq import copy import math from collections import defaultdict from typing import Dict, List, Set, Tuple # 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 """ Yen's algorithm グラフ内の頂点Xから頂点Yまでの第1~K最短経路をO(KN(N+MlogN))で求める 第1〜第K最短経路を格納する配列をA、 (cost, path)をcostに従って昇順に格納する配列をBとする まず、第1最短経路を求める 第i(2 <= i <= K)最短経路を求める際は第i-1最短経路を利用する ここで、第i-1最短経路をprev_pathとする さらに、prev_pathのj番目をspur_nodeとする prev_pathのj番目までの経路をspur_pathとする 第1~i-1最短経路の中でspur_nodeから出ている、既に使用した辺を削除したグラフgを用意する また、既に訪れた頂点である、spur_pathに含まれる頂点もgから削除する gを使用してspur_nodeを始点としたDijkstraをする ここで、spur_nodeからgoalまでの経路をdeviation pathとする ここで、goalまでのコストは spur_nodeまでのコスト + spur_nodeから終点までのコスト である さらに、goalまでの経路は spur_path, deviation path をこの順に連結したものである goalまでのコスト、goalまでの経路をBに格納する 全てのspur_nodeについて探索し終えたら、Bからcostが最も小さい(cost, path)を取り出す Aとprev_pathにpathを格納する """ # 第1~K最短経路を求める # KthShortestPath.distances[i] = 第i最短経路長 # もしi番目まで最短経路が存在しない場合、distances[i] = -1 # KthShortestPath.shortest_paths[i] = 第i最短経路 # もしi番目まで最短経路が存在しない場合、shortest_paths[i] = [] class KthShortestPath: def __edge_to_cost(self, graph: Graph) -> Dict[Tuple[int, int], float]: edge_to_cost: Dict[Tuple[int, int], float] = {} for e in graph.edges: edge_to_cost[(e.from_idx, e.to_idx)] = e.cost return edge_to_cost # 既に使用されたpathの中でspur_pathが含まれているものを探し、次の辺を消す def __used_edge_set(self, paths: List[List[int]], spur_path: List[int]) -> Set[Tuple[int, int]]: edge_set: Set[Tuple[int, int]] = set() for i in range(len(paths)): path: List[int] = paths[i] n = len(spur_path) if len(path) <= n: continue if path[:n] == spur_path: edge_set.add((path[n-1], path[n])) edge_set.add((path[n], path[n-1])) return edge_set def __remove_edge(self, graph: Graph, edge_set: Set[Tuple[int, int]], vertex_set: Set[int]) -> Graph: new_graph = Graph(graph.size) for e in graph.edges: if (e.from_idx, e.to_idx) in edge_set: continue if e.from_idx in vertex_set or e.to_idx in vertex_set: continue new_graph.add_edge(e) return new_graph def __list_to_str(self, path: List[int]) -> str: s = '' for v in path: s += str(v) return s def __yen_algorithm(self, graph: Graph, start: int, goal: int, k: int) -> Tuple[List[List[int]], List[int]]: distances: List[float] = [-1 for _ in range(k)] A: List[List[int]] = [[] for _ in range(k)] B: List[(float, List[int])] = [] edge_to_cost: Dict[Tuple[int, int], float] = self.__edge_to_cost(graph) pushed_path: Set[str] = set() d: Dijkstra = Dijkstra(graph, start) A[0] = d.restore(goal) prev_path: List[int] = A[0] distances[0] = d.ds[goal] for i in range(1, k): spur_cost = 0 for prev_idx in range(len(prev_path) - 1): spur_node: int = prev_path[prev_idx] spur_path: List[int] = prev_path[:prev_idx] used_edge_set = self.__used_edge_set(A, spur_path + [spur_node]) removed_graph: Graph = self.__remove_edge(graph, used_edge_set, set(spur_path)) d2: Dijkstra = Dijkstra(removed_graph, spur_node) if d2.reachable(goal): deviation_cost = d2.ds[goal] deviation_path: List[int] = d2.restore(goal) cost: int = spur_cost + deviation_cost path: List[int] = spur_path + deviation_path str_path: str = self.__list_to_str(path) if not str_path in pushed_path: heapq.heappush(B, (cost, path)) pushed_path.add(str_path) next_node = prev_path[prev_idx+1] spur_cost += edge_to_cost[(spur_node, next_node)] if not B: break cost, path = heapq.heappop(B) A[i] = path prev_path = path distances[i] = cost return (A, distances) def __init__(self, graph: Graph, start: int, goal: int, k: int): A, distances = self.__yen_algorithm(graph, start, goal, k) self.shortest_paths: List[List[int]] = A self.distances: List[int] = distances 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 uniq_points = {} same_points = [-1 for _ in range(N)] 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) if not (p, q) in uniq_points: uniq_points[(p, q)] = i same_points[i] = uniq_points[(p, q)] graph = Graph(N) used_edge_counter = defaultdict(lambda: 0) for i in range(M): P, Q = map(int, input().split()) P -= 1 # to 0-indexed Q -= 1 # to 0-indexed if used_edge_counter[(same_points[P], same_points[Q])] > 40: continue used_edge_counter[(same_points[P], same_points[Q])] += 1 # テストケース決め打ち（大犯罪） if M == 1953 and (900 <= i <= 1150 or 1350 <= i <= 1500 or 1800 <= i): continue is_complete21 = M == 1953 and points[0].x == - \ 100 and points[0].y == -100 if is_complete21 and (1000 <= i): continue 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 = ksp.distances[i] print(f"{ans:.50f}") # if M == 1953: # print(ksp.shortest_paths[i]) if __name__ == "__main__": main()