BOJ 11265 - 끝나지 않는 파티

문제

백준 온라인 저지 - 11265번

풀이 과정

그래프가 주어졌을 때, 최소 시간으로 각 지점간의 이동 비용을 구한 뒤 제한 시간내에 도달 가능성을 판단하는 문제입니다.
플로이드 와샬 알고리즘 을 사용해서 모든 정점간의 최소 비용을 구한 뒤 시작 지점과 도착 지점을 활용해서 답을 구할 수 있습니다.

코드

import sys


def floyd(graph):
    for k in range(N):
        for i in range(N):
            for j in range(N):
                graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])


def solution(current_party, next_party, remaining_time):
    is_possible = graph[current_party - 1][next_party - 1] <= remaining_time

    return 'Enjoy other party' if is_possible else 'Stay here'


if __name__ == '__main__':
    N, M = list(map(int, sys.stdin.readline().split()))
    graph = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
    participants = [list(map(int, sys.stdin.readline().split())) for _ in range(M)]

    floyd(graph)

    for participant in participants:
        answer = solution(*participant)
        print(answer)