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명의 학생들 중 오고 가는데 가장 오래 걸리는 학생의 소요시간을 출력한다.
- 모든 학생들의 자신의 집에서 파티 장소까지의 최단 거리를 구한다.
- 다익스트라 함수
- 입력으로 시작 노드와 그래프를 받아 최단 거리 배열을 반환
- 초기에 모든 노드의 거리를 무한대(float('inf'))로 설정하고, 시작 노드의 거리는 0으로 설정
- 최소 힙(heapq)을 사용하여 현재까지의 최단 거리와 해당 노드를 저장하는 힙을 유
- 힙이 빌 때까지 반복하며 최단 거리를 갱신하고, 인접한 노드들을 확인하여 최단 거리를 갱신
- main 함수
- 입력으로 도시의 수(N), 도로의 수(M), 시작 도시(X)를 받음
- 그 후, 도시 간의 도로 정보를 입력받아 그래프를 생성
- dijkstra 함수를 사용하여 X에서 출발하는 최단 거리를 계산하고, 이를 total_distances에 저장
- total_distances[0]을 0으로 설정하여 시작 도시에서 시작 도시로 가는 거리를 0으로 만듬
- 모든 도시에 대해 다시 dijkstra를 호출하여 X로부터 각 도시까지의 거리를 계산하고, total_distances[i]에 더해줌
- 마지막으로, total_distances 중 최댓값을 출력
- 다익스트라 문제를 여러번 풀어보면 이런 문제는 꽤 익숙하게 풀 수 있지 않을까?
- 아직은 좀 시간이 걸리는 거 같다.
import heapq
def dijkstra(start, graph):
n = len(graph)
distances = [float('inf')] * n
distances[start] = 0
heap = [(0, start)]
while heap:
current_distance, current_node = heapq.heappop(heap)
if distances[current_node] >= current_distance:
for neighbor, weight in graph[current_node]:
new_distance = current_distance + weight
if new_distance < distances[neighbor]:
distances[neighbor] = new_distance
heapq.heappush(heap, (new_distance, neighbor))
return distances
def main():
N, M, X = map(int, input().split())
city = [[] for _ in range(N + 1)]
for _ in range(M):
a, b, t = map(int, input().split())
city[a].append((b, t))
total_distances = dijkstra(X, city)
total_distances[0] = 0
for i in range(1, N + 1):
if i != X:
individual_distances = dijkstra(i, city)
total_distances[i] += individual_distances[X]
print(max(total_distances))
if __name__ == "__main__":
main()