https://www.acmicpc.net/problem/1504
1504번: 특정한 최단 경로
첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존
www.acmicpc.net
다익스트라 알고리즘을 이용하여 풀 수 있는 문제였다.
v1, v2를 지나야 하므로 가능한 경로는 두 가지 이다.
1 -> v1 -> v2 -> N
1 -> v2 -> v1 -> N
따라서 시작점을 1, v1, v2로 다익스트라를 실행하여 각각의 경우에 맞는 값을 구한 뒤 더하여 더 짧은 거리를 출력하면 된다. 경로가 없는 경우에 -1을 출력해야 한다는 것도 잊지 말아야 한다.
import sys, heapq
input = sys.stdin.readline
N, E = map(int, input().split())
graph = [[] for _ in range(N+1)]
for _ in range(E):
a, b, c = map(int, input().split())
graph[a].append([b,c])
graph[b].append([a,c])
v1, v2 = map(int, input().split())
def solve(start, end):
ans = [float('INF')]*(N+1)
ans[start] = 0
h = []
heapq.heappush(h, [ans[start], start])
while(h):
d, u = heapq.heappop(h)
if ans[u] < d:
continue #이미 방분한 경우
for v, c in graph[u]:
dist = d + c
if (dist < ans[v]):
ans[v] = dist
heapq.heappush(h, [dist, v])
return ans[end]
p1 = solve(1,v1) + solve(v1,v2) + solve(v2,N)
p2 = solve(1,v2) + solve(v2,v1) + solve(v1,N)
if (p1>=float('INF') and p2>=float('INF')):
print(-1)
else: print(min(p1,p2))
'알고리즘💻 > 우선순위큐&다익스트라' 카테고리의 다른 글
BOJ 18223번: 민준이와 마산 그리고 건우 (0) | 2021.08.21 |
---|---|
BOJ 1655번: 가운데를 말해요 (0) | 2021.08.19 |
BOJ 22116번: 창영이와 퇴근 (0) | 2021.08.17 |
BOJ 11279번: 최대 힙 (0) | 2021.02.15 |
BOJ 20046번: Road Reconstruction (0) | 2021.02.13 |