1504 - 특정한 최단 경로 / gold 4 / 다익스트라+힙

- 틀림

"""
1504 - 특정한 최단 경로 / gold 4 / 
"""
import sys, heapq

input = sys.stdin.readline
INF = int(1e9)

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))

p1, p2 = map(int, input().split())


def dijkstra(start, end):
    distance = [INF] * (n + 1)
    q = []
    heapq.heappush(q, (0, start))
    while q:
        stack_dist, node = heapq.heappop(q)

        if stack_dist > distance[node]:
            continue

        for next_node, next_dist in graph[node]:
            cost = stack_dist + next_dist
            if cost < distance[next_node]:
                distance[next_node] = cost

    return distance[end]


# 1 -> p1 -> p2 -> n
result_1 = dijkstra(1, p1) + dijkstra(p1, p2) + dijkstra(p2, n)
# 1 -> p2 -> p1 -> n
result_2 = dijkstra(1, p2) + dijkstra(p2, p1) + dijkstra(p1, n)

if result_1 >= INF and result_2 >= INF:
    print(-1)
else:
    print(min(result_1, result_2))

 

- 정답

"""
1504 - 특정한 최단 경로 / gold 4 / 다익스트라+힙
"""
import sys, heapq

input = sys.stdin.readline
INF = int(1e9)

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 dijkstra(start):
    distance = [INF] * (n + 1)
    distance[start] = 0
    q = []
    heapq.heappush(q, (0, start))
    while q:
        stack_dist, node = heapq.heappop(q)

        if stack_dist > distance[node]:
            continue

        for next_node, next_dist in graph[node]:
            cost = stack_dist + next_dist
            if cost < distance[next_node]:
                distance[next_node] = cost
                heapq.heappush(q, (cost, next_node))

    return distance


dist_1 = dijkstra(1)
dist_v1 = dijkstra(v1)
dist_v2 = dijkstra(v2)
# 1 -> v1 -> v2 -> n
result_1 = dist_1[v1] + dist_v1[v2] + dist_v2[n]
# 1 -> v2 -> v1 -> n
result_2 = dist_1[v2] + dist_v2[v1] + dist_v1[n]
min_result = min(result_1, result_2)

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

 

처음에 문제 접근 방식은 정답과 비슷하게 코드를 짰다

 

하지만, dijkstra 함수에서 distance[start] = 0 빼먹음

 

또한 마지막 계산 과정에서 dijkstra 함수를 6번 부른 것을 3번 함수를 부르게 다시 개선

출력시 코드도 개선