[Python][백준] 1238_파티

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

1238번: 파티

문제

N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다.

어느 날 이 N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 있고 i번째 길을 지나는데 Ti(1 ≤ Ti ≤ 100)의 시간을 소비한다.

각각의 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 한다. 하지만 이 학생들은 워낙 게을러서 최단 시간에 오고 가기를 원한다.

이 도로들은 단방향이기 때문에 아마 그들이 오고 가는 길이 다를지도 모른다. N명의 학생들 중 오고 가는데 가장 많은 시간을 소비하는 학생은 누구일지 구하여라.

 

입력

첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어온다. 시작점과 끝점이 같은 도로는 없으며, 시작점과 한 도시 A에서 다른 도시 B로 가는 도로의 개수는 최대 1개이다.

모든 학생들은 집에서 X에 갈수 있고, X에서 집으로 돌아올 수 있는 데이터만 입력으로 주어진다.

 

출력

첫 번째 줄에 N명의 학생들 중 오고 가는데 가장 오래 걸리는 학생의 소요시간을 출력한다.

---

모든 정점(학생)으로부터 X번 마을까지의 왕복거리를 구하여 그 중에서 최대값을 선택하여야 하는 문제이다.

처음에는 플로이드-워샬(Floyd-Warshall) 알고리즘을 시도했는데, 최대 N = 1000일 때, O(1000^3) 이 되기 때문에 역시나 시간초과였다.

대신에 1~N번 학생의 가는 길, 오는 길 각각 다익스트라(Dijkstra) 로 최단거리의 합을 구하여 그 중 최대값을 찾아주었다.

 

import sys, heapq

### Dijkstra
def dijkstra(s, e): # s -> e 까지 최소
    
    dist = [ sys.maxsize for _ in range(N)]
    dist[s] = 0

    que = []
    heapq.heappush(que, [0, s])

    while len(que) > 0 :
        t, ss = heapq.heappop(que)
        for tt, ee in arr[ss]:
            if dist[ee] > dist[ss] + tt:
                dist[ee] = dist[ss] + tt
                heapq.heappush(que, [dist[ee], ee])

    # print(s, "->", e, dist[e])
    return dist[e]

### MAIN
N, M, X = map(int, sys.stdin.readline().strip().split())
arr = [ [] for _ in range(N)]

for _ in range(M): # 간선정보 업데이트
    s, e, t = map(int, sys.stdin.readline().strip().split())
    arr[s-1].append((t, e-1))

maxLen = 0 # 최대 경로
for n in range(N):
    maxLen = max(maxLen, dijkstra(n, X-1) + dijkstra(X-1, n)) # 가는길, 오는길 각각 dijkstra

print(maxLen)


###########
### Floyd-warshall 은 시간초과
# N, M, X = map(int, sys.stdin.readline().strip().split())
# arr = [[ sys.maxsize for _ in range(N)] for _ in range(N)] # 모든 경로를 저장하는 2차원 배열

# for _ in range(M): # 간선정보 업데이트
#     s, e, t = map(int, sys.stdin.readline().strip().split())
#     arr[s-1][e-1] = t

# for n in range(N):
#     arr[n][n] = 0

# # floyd-warshall
# for i in range(N):
#     for j in range(N):
#         for k in range(N):
#             arr[i][j] = min(arr[i][j], arr[i][k] + arr[k][j]) # 최소 경로 갱신

# # 제일 오래걸리는 학생의 소요시간 구하기
# dist = []
# for n in range(N):
#     dist.append(arr[n][X-1] + arr[X-1][n])

# print(sorted(dist)[N-1])