dijkstra
https://www.acmicpc.net/problem/1504
풀이 방법
결국 처음→ V1→V2→N 과 처음→V2→V1→N으로 가는 경우의 수 중에서 가장 거리가 짧은 경우를 구하는 것이다. 점과 점 사이의 거리를 구해야 하기 때문에 다익스트라 알고리즘을 이용해서 풀어야 했다. 근데 점과 점 사이의 거리를 6번 구해야 하니, 함수로 만들어서 start, end 값을 주면 최소 거리를 구할 수 있게 하였다.
import heapq
N, E = map(int, input().split())
edges = [[] for _ in range(N+1)]
for _ in range(E):
a, b, c = map(int, input().split())
edges[a].append((c, b))
edges[b].append((c, a))
v1, v2 = map(int, input().split())
INF = float("inf")
def dijkstra(start, end, edges):
dists = [INF] * (N + 1)
dists[start] = 0
pq = [(0, start)]
while pq:
dist, node = heapq.heappop(pq)
if dists[node] < dist:
continue
for next_dist, next_node in edges[node]:
if dists[next_node] > next_dist + dist:
dists[next_node] = next_dist + dist
heapq.heappush(pq, (next_dist + dist, next_node))
return dists[end]
one = dijkstra(1, v1, edges) + dijkstra(v1, v2, edges) + dijkstra(v2, N , edges)
two = dijkstra(1, v2, edges) + dijkstra(v2, v1, edges) + dijkstra(v1, N , edges)
if min(one, two) == INF:
print(-1)
else:
print(min(one, two))
후기
풀이 방법을 생각해내는 것은 어렵지 않았다. 다익스트라를 오랫만에 구현하는게 어려웠을 뿐