https://www.acmicpc.net/problem/1504

두 점 반드시 거쳐서 1부터 n까지 가는 최단 거리를 구하는 문제이다.

특정 점에서 시작한 최단 거리를 구하는 문제였기에 다익스트라를 사용했다.

BFS는 가중치가 있는 그래프에서 모든 경로를 동일하게 판단하기에 불필요한 탐색이 많아서 적절하지 않고 실제로 시간초과 발생
네트워크 복구 문제에서 최단 거리와 MST를 구분하지 않아서 헤맸음

s - v1 - v2 - n, s - v2 - v1 - n 이 두 가지 경우를 생각했다.

처음에 1에서 n으로 바로 가는 경우에 v1, v2가 있는 경우를 생각해야하지 않을까 싶었으나
1에서 바로 n으로 가는데 가는길에 v1, v2가 있는 최단거리나
1에서 v1, v1에서 v2, v2에서 n으로 가는 최단거리나 같을 것이라는 생각이 들어서 그대로 진행했다.

Python

시도 1 - 75% 실패

import sys
from heapq import *

input = sys.stdin.readline

def dij(start, end, n, edges):
    que = []
    dist = [200000 * 800 * 1000 * 2 for _ in range(n + 1)]

    que.append((0, start))
    dist[start] = 0

    while que:
        cost, now = heappop(que)

        if dist[now] < cost:
            continue

        for next, d in edges[now]:
            if dist[next] > cost + d:
                dist[next] = cost + d
                heappush(que, (dist[next], next))

    return dist[end]


n, m = map(int, input().split())

edges = [[] for _ in range(n + 1)]
for a, b, c in [map(int, input().split()) for _ in range(m)]:
    edges[a].append((b, c))
    edges[b].append((a, c))

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

v12 = dij(v1, v2, n, edges)

s1 = dij(1, v1, n, edges)
s2 = dij(1, v2, n, edges)

e1 = dij(v1, n, n, edges)
e2 = dij(v2, n, n, edges)

print(min(s1 + v12 + e2, s2 + v12 + e1))

시도 2

import sys
from heapq import *

input = sys.stdin.readline
limit = 200000 * 800 * 1000 * 2


def dij(start, end, n, edges):
    que = []
    dist = [limit for _ in range(n + 1)]

    que.append((0, start))
    dist[start] = 0

    while que:
        cost, now = heappop(que)

        if dist[now] < cost:
            continue

        for next, d in edges[now]:
            if dist[next] > cost + d:
                dist[next] = cost + d
                heappush(que, (dist[next], next))

    return dist[end]


n, m = map(int, input().split())

edges = [[] for _ in range(n + 1)]
for a, b, c in [map(int, input().split()) for _ in range(m)]:
    edges[a].append((b, c))
    edges[b].append((a, c))

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

v12 = dij(v1, v2, n, edges)

s1 = dij(1, v1, n, edges)
s2 = dij(1, v2, n, edges)

e1 = dij(v1, n, n, edges)
e2 = dij(v2, n, n, edges)

ans = min(s1 + v12 + e2, s2 + v12 + e1)

print(ans if ans < limit else -1)

간선이 없는 경우를 생각 안 했다. 간선 없는 경우 추가하니까 성공했다.