[boj] 11265_끝나지 않는 파티_python

문제링크

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

11265번: 끝나지 않는 파티

---

문제설명

문제

입력

1 : 파티장의 크기 N(5 ≤ N ≤ 500)과 서비스를 요청한 손님의 수 M(1 ≤ M ≤ 10,000)

2 ~ N+1 : 인접 리스트의 거리 정보가 N * N만큼 주어짐.

i번째 줄의 j번째 수 T(1 ≤ T ≤ 1,000,000)는 i번 파티장에서 j번 파티장으로 직접적으로 연결된 도로를 통해 이동하는 시간을 의미 

N+2~ : M개의 줄만큼 세개의 정수 A, B, C가 주어진다. 

 

출력

M개의 줄에 걸쳐 서비스를 요청한 손님이 시간내에 다른 파티장에 도착할 수 있으면 “Enjoy other party”를, 시간내에 도착할 수 없으면 "Stay here”를 출력한다.

 

조건

• (5 ≤ N ≤ 500), (1 ≤ M ≤ 10,000)
• A(1 ≤ A ≤ N) 는 서비스를 요청한 손님이 위치한 파티장의 번호, B(1 ≤ B ≤ N) 다음 파티가 열리는 파티장의 번호, C(1 ≤ C ≤ 1,000,000,000)는 지금으로부터 다음 파티가 열리는데 걸리는 시간을 의미

---

문제풀이

# 50분
# 시간 복잡도 : O(N³+M) # 플루이드-워셜 + 파티장 출력 부분
# 공간 복잡도 : O((N+1)²) # 그래프
import sys

input = sys.stdin.readline
# 파티장 크기 N(5 ≤ N ≤ 500), 서비스 요청한 손님 수 M(1 ≤ M ≤ 10,000)
N, M = map(int, input().split())
# 그래프의 크기 N * N. 0번째 인덱스는 무시
graph = [[0 for _ in range(N + 1)] for _ in range(N + 1)]

# 인접 리스트 : N개의 줄에 걸쳐 각각 N개의 수가 주어진다.
for i in range(1, N + 1):
    lst = list(map(int, input().split()))
    for j in range(1, N + 1):
        graph[i][j] = lst[j - 1]


# 플루이드-워셜 진행
def floyd_warshall():
    for i in range(1, N + 1):
        for j in range(1, N + 1):
            for k in range(1, N + 1):
                # 두 가지 경우를 비교한다 : j -> k vs j -> i -> k
                graph[j][k] = min(graph[j][k], graph[j][i] + graph[i][k])


floyd_warshall()
for i in range(M):
    Y, X, W = map(int, input().split())
    # 해당 위치의 가중치가 W 이하일 때
    # 서비스를 요청한 손님이 시간 내에 다른 파티장에 도달할 수 있는 경우
    if graph[Y][X] <= W:
        print("Enjoy other party")
    # 해당 위치의 가중치가 W 이상일 때
    # 서비스를 요청한 손님이 시간 내에 다른 파티장에 도달할 수 없는 경우
    else:
        print("Stay here")