11265_끝나지 않는 파티

입력

첫째 줄에는 정점의 개수(N), 정답을 요구하는 문제 개수(M) 입력
둘째 줄부터 N+1번째 줄까지 정점들에 대한 cost 그래프 입력
N+2번째 줄부터 N+M+1번째 줄까지 정답을 요구하는 문제 입력

출력

주어진 문제에 대한 각각의 정답을 출력
해당 cost안에 도착점까지 도달 가능하면 "Enjoy other party" 출력
해당 cost안에 도착점까지 도달 불가능하면 "Stay here" 출력

조건

• 제한 시간 2초
• 최대 정점의 개수 500개

풀이

제한 시간이 2초이고 최대 정점의 개수가 500개 이기 때문에 플로이드-워셜 알고리즘으로 풀이 가능

1. 각각의 정점들의 cost값을 입력받고 만약 cost가 0인 경우 cost의 최대값인 1000000000보다 1더 큰 1000000001으로 설정

for row in range(N):
    map_.append(list(map(int, sys.stdin.readline().split())))

    for col in range(N):
        if map_[row][col] == 0: map_[row][col] = 1000000001

2. 삼중 for문을 돌며 최소값으로 map_을 채움

for k in range(N):
    for i in range(N):
        for j in range(N):
            if (map_[i][k] + map_[k][j]) < map_[i][j]: map_[i][j] = (map_[i][k] + map_[k][j])

3. 최종 map_의 cost와 요청한 cost를 비교하여 답을 출력

for _ in range(M):
    i, j, cost = map(int, sys.stdin.readline().split())

    if map_[i-1][j-1] <= cost: print("Enjoy other party")
    else: print("Stay here")

처음에 시간 초과가 발생하였는데 풀이의 3번 과정에서 for문을 돌 때 변수를 지정하지 않는 것으로 해결하였다.

전체 코드

끝나지 않는 파티