# verification-helper: PROBLEM https://yukicoder.me/problems/no/1069 import sys 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 __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) 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[k] = kth path used_path: List[List[int]] = [] self.dists.append(first_cost) self.shortest_paths.append(first_path) prev_path = first_path used_path.append(first_path) # 各頂点ごとに使用した辺を格納しておくO(K(N+M)) # used_edges[v] = [Edge(), Edge()] # used_edges: List[List[Edge]] # 各頂点ごとにグラフを持つO(N(N+M)) # 辺の管理が楽になる # graphs: List[Graph] graphs: List[Graph] = [g for _ in range(n)] # 2番目〜K番目の最短経路を求めるO(K) for _ in range(k-1): # (prev_path[i], prev_path[i+1]) の辺を消すO(N) for i in range(len(prev_path)-1): spur_node = prev_path[i] # O(M+N) edges = graphs[spur_node].edges new_graph = Graph(n) # ここでprev_path[i],prev_path[i+1] の辺を消すだけで良い for j in range(len(edges)): edge = edges[j] if edge.from_idx == prev_path[i] and edge.to_idx == prev_path[i+1]: continue new_graph.add_edge(edge) graphs[spur_node] = new_graph spur_d = Dijkstra(graphs[spur_node], spur_node) cost = d.ds[spur_node] + spur_d.ds[goal] i = prev_path.index(spur_node) spur_root = prev_path[:i] path = spur_root + spur_d.restore(goal) if path in used_path: continue heapq.heappush(pq, (cost, path)) used_path.append(path) if not pq: break cost, path = heapq.heappop(pq) 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 = [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:.6f}") if __name__ == "__main__": main()