1504

날짜 : 2023. 03. 13

사용 언어 : python

 

문제

 

 

코드

import sys
import heapq

n, e = map(int, sys.stdin.readline().split())  # 정점, 간선의 개수
graph = [[] for _ in range(n + 1)]
dist = [int(1e9)] * (n + 1)

for _ in range(e):
    a, b, c = map(int, sys.stdin.readline().split())  # 시작, 도착, 거리
    graph[a].append([b, c])  # 방향성 없음 -> 양쪽으로 추가
    graph[b].append([a, c])

v1, v2 = map(int, sys.stdin.readline().split())
route1, route2 = 0, 0


def dijkstra(start):
    q = []
    heapq.heappush(q, (0, start))
    dist[start] = 0
    while q:
        d, now = heapq.heappop(q)
        if dist[now] < d: continue
        for node in graph[now]:
            cost = d + node[1]
            if cost < dist[node[0]]:
                dist[node[0]] = cost
                heapq.heappush(q, (cost, node[0]))
    return


dijkstra(1)
route1 += dist[v1]  # 1 -> v1
route2 += dist[v2]  # 1 -> v2
dist = [int(1e9)] * (n + 1)
dijkstra(v1)
route1 += dist[v2]  # v1 ->
route2 += dist[n]
dist = [int(1e9)] * (n + 1)
dijkstra(v2)
route1 += dist[n]
route2 += dist[v1]
res = min(route1, route2)
if res >= int(1e9):
    print(-1)
else:
    print(res)

 

 

풀이

- 다익스트라를 활용해서 각각의 경로를 구한다.

- 또한 각 노드간 방향성이 존재하지 않기 때문에 각 노드별로 값을 삽입한다.

- v1, v2를 모두 거쳐가는 경우를 따져야 하기 때문에 (v1, v2) 순서로 거쳐가거나 (v2, v1) 순서로 거쳐간다.

=> 1(시작) -> v1 -> v2 -> n(도착)

     1(시작) -> v2 -> v1 -> n(도착)

- 즉, 위 두 가지 루트를 확인하기 위해 1에서 출발했을 때 다익스트라를 수행 후 v1, v2의 최단거리를 구하고, v1, v2에 대하여 각각 다익스트라를 수행한 다음 그에 맞는 값들을 구하여 route1, route2에 더한 후 값을 구한다.

- 또한 값이 나오지 않는 경우도 발생할 수 있기 때문에 조건도 넣음으로써 분기한다.

동그라이 부분을 각각 더하여 값을 비교한다

 

알게된 점

- 

 

 

참고 사이트

-