다익스트라 알고리즘을 여러번 사용하면 답을 찾을 수 있다.
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)
다익스트라 안보고 짤 수 있을때까지 연습해야겠다.
시간없어서 급하게 짰는데 반복되는 로직 함수 안에 집어넣어야 할듯 ㅎㅎ.. 너무 더럽게썼다
벽 부수기 문제도 올려주세요. 저 그거 잘 모르겠어요..!