[백준] 11265번 끝나지 않는 파티 _ Python

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

11265번: 끝나지 않는 파티

 

 

[초기 접근 방법]

- M명의 사람들의 출발점이 모두 다르다.

   → 따라서 플로이드 알고리즘으로 모든 노드 간의 최단거리를 구한다.

 

1. A 시작점에서 B 지점까지의 최단 경로를 구한다.

2. 위 최단 경로가 C 오픈 시간보다 빠르면 → 파티장에 도착할 수 있다:

                                                      길면 → 파티장에 도착할 수 없다.

 

 

[생각]

- 다익스트라나 벨만 포드에 비해, 구현이 직관적이며 간단하다.

 

 

[코드]

# 틀린 이유
# - 빠른 입출력을 하지 않음
# - open_time에서 등호를 빼 먹었다

# 풀이 시간 : 30분
# 시간복잡도 : O(N^3)
# 공간복잡도 : O(N^2)
# 참고 : -

import sys
input = sys.stdin.readline

# 파티장의 크기, 서비스를 요청한 손님의 수
N, M = map(int, input().split())

# i에서 j까지 이동하는데 걸리는 시간
road = [list(map(int, input().split())) for _ in range(N)]

# A : 손님이 위치한 파티장 번호 / B : 다음 파티가 열리는 파티장 번호 / C : 지금으로부터 다음 파티가 열리는데 걸리는 시간
party = [list(map(int, input().split())) for _ in range(M)]

# 모든 노드 간의 최단거리를 구한다.
for k in range(N):
    for i in range(N):
        for j in range(N):
            road[i][j] = min(road[i][j], road[i][k] + road[k][j])


for start, end, open_time in party:
    # 이동 시간 vs 오픈 시간
    # 오픈하기 전에 미리 도착해 있어야 한다.
    if road[start-1][end-1] <= open_time: # road[][], graph[][] 0 인덱스 맞추기 위함
        print("Enjoy other party")
    # 기다리는 시간이 더 짧다.
    else:
        print("Stay here")