문제
예제 입력
첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어온다. 시작점과 끝점이 같은 도로는 없으며, 시작점과 한 도시 A에서 다른 도시 B로 가는 도로의 개수는 최대 1개이다.
모든 학생들은 집에서 X에 갈수 있고, X에서 집으로 돌아올 수 있는 데이터만 입력으로 주어진다.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 3
예제 출력
첫 번째 줄에 N명의 학생들 중 오고 가는데 가장 오래 걸리는 학생의 소요시간을 출력한다.
10
출발지에서 목적지까지의 거리를 반환하는 다익스트라 최단거리 알고리즘을 통해 각 학생들의 위치와 파티장소의 왕복 소요시간을 구해 더한 후 가장 큰 값을 출력한다.
import sys
from heapq import*
input = sys.stdin.readline
INF = int(1e9)
n, m, party = map(int, input().split())
graph = [[] for _ in range(n + 1)]
for _ in range(m):
a, b, c = map(int, input().split())
graph[a].append((b, c))
def dijkstra(start, dest):
distance = [INF] * (n + 1)
q = []
heappush(q, (0, start))
distance[start] = 0
while q:
dist, now = heappop(q)
if distance[now] < dist:
continue
for i in graph[now]:
cost = dist + i[1]
if cost < distance[i[0]]:
distance[i[0]] = cost
heappush(q, (cost, i[0]))
return distance[dest]
ansList = []
for i in range(1, n + 1):
a = dijkstra(party, i) + dijkstra(i, party)
ansList.append(a)
print(max(ansList)) 