난이도
문제
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명의 학생들 중 오고 가는데 가장 오래 걸리는 학생의 소요시간을 출력한다.
예제
입력 출력 4 8 2
1 2 4
1 3 2
1 4 7
2 1 1
2 3 5
3 1 2
3 4 4
4 2 310
풀이
답을 알고나니 참 쉬운 문제이다.
우선 일반적인 다익스트라 문제인데, 계속 메모리 초과가 발생하더라,, 도대체 왜? 메모리를 잡아 먹을만한 배열을 전부 없애줬는데도 계속 메모리 초과..
도저히 모르겠어서 강의를 찾아봤는데, 아뿔싸 문제를 제대로 안읽었더라.
나는 파티 장소가 정해져 있는 것이 아니라 모든 정점이 파티 장소가 될 수 있다고 생각하고 풀이를 했는데 입력으로 들어오는 X 가 파티 장소였던 것...
그리고 강의를 들으면서 한 가지 알아낸 점은 방향이 있는 그래프의 방향을 반대로 입력하고, 반대 그래프의 다익스트라를 구하면 도착지에서 출발지 까지 가는 최소 거리를 구할 수 있다.
그래서 이 문제는 두번의 다익스트라로 문제를 풀 수 있다.
출발지 -> 도착지 의 다익스트라
도착지 -> 출발지 의 다익스트라 (그래프의 정점을 반전하면 됨)
코드
from sys import stdin
from heapq import heappop, heappush
input = stdin.readline
def dijkstra(start, distance, graph):
heap = []
heappush(heap, (0, start))
distance[start] = 0
while heap:
cost, now = heappop(heap)
if distance[now] < cost:
continue
for node in graph[now]:
next_cost = cost + node[0]
if next_cost < distance[node[1]]:
distance[node[1]] = next_cost
heappush(heap, (next_cost, node[1]))
def solution():
N, M, X = map(int, input().split())
graph = [[] for _ in range(N+1)]
reversed_graph = [[] for _ in range(N+1)]
for _ in range(M):
S, E, C = map(int, input().split())
graph[S].append((C, E))
reversed_graph[E].append((C, S))
distance = [2e9 for _ in range(N+1)]
reversed_distance = [2e9 for _ in range(N+1)]
dijkstra(X, distance, graph)
dijkstra(X, reversed_distance, reversed_graph)
max_cost = 0
for x, y in zip(distance[1:], reversed_distance[1:]):
max_cost = max(max_cost, x+y)
return max_cost
print(solution())
