#779907 (PyPy3) No.1069 電柱 / Pole (Hard)

• 問題: No.1069 電柱 / Pole (Hard)
• ユーザー: matumoto
• 提出日時: 2022-07-21 21:04:11
• 言語: PyPy3 (7.3.15)
• 結果: TLE
• 実行時間: -
• コード長: 10,055 bytes
• コンパイル時間: 191 ms
• コンパイル使用メモリ: 82,432 KB
• 実行使用メモリ: 277,948 KB
• 最終ジャッジ日時: 2024-07-03 04:59:41
• 合計ジャッジ時間: 4,335 ms
• ジャッジサーバーID （参考情報）: judge3 / judge5

ファイルパターン	結果
sample	AC * 4
other	TLE * 1 -- * 78

ソースコード

# 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)

                used_vetex_set = set(prev_path[:i])

                # ここでprev_path[i],prev_path[i+1]の辺を消すだけで良い
                # prev_path[:i]に含まれる頂点も消したい？
                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

                    if edge.from_idx in used_vetex_set or edge.to_idx in used_vetex_set:
                        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()