[python]伯俊11265-終わらないチームの解答

Overview

BOJ 11265番未完のチームPython回答
分類:最短パス、Dijkstra、Floyd-Warshall

質問ページ

https://www.acmicpc.net/problem/11265

プールコード1-floydとshall

from sys import stdin
from typing import List


def floyd_warshall(n: int, graph: List[List[int]]) -> None:
    for k in range(1, n + 1):
        for i in range(1, n + 1):
            for j in range(1, n + 1):
                if graph[i][k] + graph[k][j] < graph[i][j]:
                    graph[i][j] = graph[i][k] + graph[k][j]


def main():
    def input():
        return stdin.readline().rstrip()

    n, m = map(int, input().split())
    graph = [[0] * (n + 1)] + \
            [[0] + list(map(int, input().split())) for _ in range(n)]

    floyd_warshall(n, graph)

    for _ in range(m):
        a, b, c = map(int, input().split())
        if graph[a][b] <= c:
            print("Enjoy other party")
        else:
            print("Stay here")


if __name__ == "__main__":
    main()

floodとshallアルゴリズムを用いて,各キャプテンに移動するのに要する最短時間を求める.

プールコード2-マルチアウトレット

from sys import stdin
from typing import List
from heapq import heappop, heappush


n: int
m: int
graph: List[List[int]]


def dijkstra(start: int, dest: int, time: int) -> bool:
    if graph[start][dest] <= time:
        return True

    hq = []
    for i in range(1, n + 1):
        if i != start:
            heappush(hq, (graph[start][i], i))

    while hq:
        dist, node = heappop(hq)
        if dist > time:
            return False

        if dist > graph[start][node]:
            continue

        for neighbor in range(1, n + 1):
            if neighbor == node:
                continue
            if dist + graph[node][neighbor] < graph[start][neighbor]:
                graph[start][neighbor] = dist + graph[node][neighbor]
                heappush(hq, (graph[start][neighbor], neighbor))
            if neighbor == dest and graph[start][neighbor] <= time:
                return True

    return False


def main():
    def input():
        return stdin.readline().rstrip()
    global n, m, graph

    n, m = map(int, input().split())
    graph = [[0] * (n + 1)] + \
            [[0] + list(map(int, input().split())) for _ in range(n)]

    for _ in range(m):
        a, b, c = map(int, input().split())
        if dijkstra(a, b, c):
            print("Enjoy other party")
        else:
            print("Stay here")


if __name__ == "__main__":
    main()

多芸樹を利用した草です.採点結果はpypy 3に合格したが、python 3はタイムアウトした.
お客様がパーティー会場に移動するたびに、dijkstra関数を実行し、時間内に目的地に移動できるかどうかを判断します.