#287 백준 파이썬 [1238] 파티 - 플로이드 와샬

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

 

SOLUTION

플로이드 와샬 알고리즘으로 풀 수 있는 문제. 다익스트라 알고리즘으로도 풀 수 있지만, pypy로 컴파일 해가면서 까지기어코 플로이드 와샬로 풀었다.

문제의 풀이 해결 및 코드는 https://claude-u.tistory.com/334 와 같다.

또한 통과를 위해 pypy로 제출하였다.

PYTHON CODE

import sys

#입력
N, M, X = map(int, input().split())
distance = [[M * 100 for _ in range(N+1)] for _ in range(N+1)]
for _ in range(M):
    start, end, time = map(int, sys.stdin.readline().split())
    distance[start][end] = time


#플로이드 와샬 알고리즘
for k in range(1, N+1): #경로 for문이 가장 상위 단계여야 누락되지 않는다
    for i in range(1, N+1):
        if distance[i][k] != M * 100:
            for j in range(1, N+1):
                if i == j: #자기 자신일 경우
                    distance[i][j] = 0 
                else:
                    distance[i][j] = min(distance[i][j],
                                         distance[i][k] + distance[k][j])


#출력
max_time = 0
for i in range(1, N+1):
    max_time = max(max_time,
                   distance[i][X] + distance[X][i])
print(max_time)