백준 1504번 특정한 최단 경로

백준 1504번: 특정한 최단 경로

아이디어

다익스트라 알고리즘을 여러번 사용하면 답을 찾을 수 있다. 1->v1->v2->N / 1->v2->v1->N 두 가지 경우중 더 적은 비용으로 N까지 도달하는 경우가 정답이다.

코드

import heapq
import sys

input = sys.stdin.readline

INF = 987654321

V, E = map(int, input().split())
init = 1

graph = [[] for _ in range(V + 1)]

for _ in range(E):
    u, v, w = map(int, input().split())
    graph[u].append((v, w))
    graph[v].append((u, w))

def dijkstra(start):
    q = []
    heapq.heappush(q, (0, start))
    while q:
        c, t = heapq.heappop(q)
        if c > dist[t]:
            continue
        for i in graph[t]:
            if dist[i[0]] > c + i[1]:
                dist[i[0]] = c + i[1]
                heapq.heappush(q, (c + i[1], i[0]))

v1, v2 = map(int, input().split())

res1 = 0

dist = [INF] * (V + 1)
dist[init] = 0
dijkstra(init)
res1 += dist[v1]

dist = [INF] * (V + 1)
dist[v1] = 0
dijkstra(v1)
res1 += dist[v2]

dist = [INF] * (V + 1)
dist[v2] = 0
dijkstra(v2)
res1 += dist[V]

res2 = 0

dist = [INF] * (V + 1)
dist[init] = 0
dijkstra(init)
res2 += dist[v2]

dist = [INF] * (V + 1)
dist[v2] = 0
dijkstra(v2)
res2 += dist[v1]

dist = [INF] * (V + 1)
dist[v1] = 0
dijkstra(v1)
res2 += dist[V]

res = min(res1, res2)

if res >= INF:
    print(-1)
else:
    print(res)

여담

다익스트라 안보고 짤 수 있을때까지 연습해야겠다. 시간없어서 급하게 짰는데 반복되는 로직 함수 안에 집어넣어야 할듯 ㅎㅎ.. 너무 더럽게썼다