백준 1504 특정한 최단 경로

과정

• 다익스트라
• 1 - v1 - v2 - N 또는 1 - v2 - v1 - N 의 순서로 이동하는 최단 경로 중, 작은 수를 출력한다.
• 다익스트라를 구현해서, 1부터 시작하는 최단거리, v1 또는 v2에서 시작하는 최단 거리, N에서 시작하는 최단 거리를 구하고, 조건에 부합하는 경로 중 최솟값을 출력한다.

import sys
import heapq

sys.stdin = open("input.txt")

N, E = map(int, input().split())
INF = 1e9

graph = [[] for _ in range(N)]

for _ in range(E):  # 연결 노드의 정보를 (노드, 가중치) 꼴로 저장
    a, b, c = map(int, input().split())
    # 방향성이 없다고 했으니까 양 방향에 대해 저장
    graph[a - 1].append((b - 1, c))
    graph[b - 1].append((a - 1, c))


def dijkstra(start):
    # initialization
    distance = [INF] * N
    q = []
    heapq.heappush(q, (0, start))
    distance[start] = 0
    # q 에서 하나씩 빼면서 확인
    while q:
        dist, now = heapq.heappop(q)
        # 이미 처리된 곳이면 무시
        if distance[now] < dist:
            continue
        # 연결된 모든 노드에 대해서 확인
        for i in graph[now]:
            cost = i[1] + dist
            if distance[i[0]] > cost:
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))
    return distance


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

distance_start = dijkstra(0)
start_v1 = distance_start[v1 - 1]
start_v2 = distance_start[v2 - 1]

distance_v = dijkstra(v1 - 1)
v1_v2 = distance_v[v2 - 1]

distance_end = dijkstra(N - 1)
v1_end = distance_end[v1 - 1]
v2_end = distance_end[v2 - 1]

ans = min(start_v1 + v1_v2 + v2_end, start_v2 + v1_v2 + v1_end)

if ans < INF:
    print(ans)
else:
    print(-1)

시행착오

• 입력 최대 정점의 개수가 작아서 플루이드워셜을 해보려했는데, 시간제한 때문에 오답이 나왔다.
• 입력 노드는 1부터 시작하지만 나는 인덱스를 사용하므로 0부터 시작해야해서 모든 노드 입력은 -1을 해야 했다.
• 최단 경로가 없을 때 -1을 출력해야한다 - 문제 잘 읽기
  • 답이 INF와 같을 때만 -1을 출력하면 안된다.
  • 각 최단 경로를 더했기 때문에 나올 수 있는 최대값은 3*INF가 된다. 출력 주의