문제 설명
•
양방향 그래프가 주어지면, 1번에서 번 정점으로 가는 최단 경로의 길이를 구하는 문제
◦
단, 정점 과 를 반드시 거쳐서 1번에서 번 정점으로 가야 한다.
◦
한번 이동했던 간선도 다시 이동할 수 있다.
예제 입력/출력
•
입력1
4 6
1 2 3
2 3 3
3 4 1
1 3 5
2 4 5
1 4 4
2 3
Plain Text
복사
•
출력1
7
Plain Text
복사
제약 조건
•
1 ≤ ≤ 800
◦
: 정점의 개수
•
1 ≤ ≤ 200,000
◦
: 간선의 개수
◦
간선의 가중치
문제 풀이
•
다익스트라 알고리즘을 이용하여 문제를 해결하면 된다. -
◦
모든 간선의 가중치가 0 이상이므로 다익스트라 알고리즘 사용 가능
◦
다음 두 경로 중 최단 경로를 선택한다.
1.
1번 노드 → 노드 → 노드 → 번 노드
2.
1번 노드 → 노드 → 노드 → 번 노드
◦
그러기 위해서는, 다익스트라 알고리즘을 총 3번 사용해주어야 한다.
1.
1번 노드를 시작점으로 하는 다익스트라 알고리즘
2.
노드를 시작점으로 하는 다익스트라 알고리즘
3.
노드를 시작점으로 하는 다익스트라 알고리즘
예제 코드
풀이 코드
import sys
input = lambda: sys.stdin.readline().rstrip()
from queue import PriorityQueue
INF = int(1e12)
def dijkstra(start_node):
global N, adj_list
dist = [INF for _ in range(N + 1)]
pq = PriorityQueue()
dist[start_node] = 0
pq.put((0, start_node)) # (dist, node)
while not pq.empty():
cur_dist, cur_node = pq.get()
for adj_node, adj_dist in adj_list[cur_node]:
temp_dist = cur_dist + adj_dist
if (temp_dist < dist[adj_node]):
dist[adj_node] = temp_dist
pq.put((temp_dist, adj_node))
return dist
# Input
N, E = map(int, input().split()) # node, edge
adj_list = [[] for _ in range(N + 1)]
for _ in range(1, E + 1):
a, b, c = map(int, input().split())
adj_list[a].append((b, c))
adj_list[b].append((a, c))
v1, v2 = map(int, input().split())
# Solve (다익스트라)
dist_1 = dijkstra(1)
dist_v1 = dijkstra(v1)
dist_v2 = dijkstra(v2)
case1 = dist_1[v1] + dist_v1[v2] + dist_v2[N] # 1 -> v1 -> v2 -> N
case2 = dist_1[v2] + dist_v2[v1] + dist_v1[N] # 1 -> v2 -> v1 -> N
ans = min(case1, case2)
print(ans if ans < INF else -1)
Python
복사