백준 11265 <끝나지 않는 파티> Python

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

---

워셜-플로이드 알고리즘 문제입니다.

 

매번 다른 노드에서 다른 노드로 최단거리를 알아내야 하는 문제를 접했을 때, 다익스트라를 여러 번 사용하기 보다 한번에 모든 노드에서 모든 노드로 향하는 최단거리를 구할 때 보다 효율적인 경우가 있습니다.

 

그런 경우에 벨만-포드 알고리즘이나 워셜-플로이드 알고리즘을 활용할 수 있습니다.

---

import sys

input = sys.stdin.readline


def solution(N, M, edges, querys):
    ### 최단거리 업데이트
    ## 플로이드-워셜
    # 거쳐갈 노드
    for mid in range(N):
        # 출발 노드
        for start in range(N):
            # 끝 노드
            for end in range(N):
                edges[start][end] = min(edges[start][end], edges[start][mid] + edges[mid][end])
    
    # 쿼리 처리
    for A, B, C in querys:
        # 시간 비교
        if edges[A-1][B-1] <= C:
            print('Enjoy other party')
        
        else:
            print("Stay here")


# 입력
N, M = map(int, input().strip().split())
edges = [list(map(int, input().strip().split())) for _ in range(N)]
querys = [list(map(int, input().strip().split())) for _ in range(M)]

solution(N, M, edges, querys)