193. 거의 최단 경로

백준

1. 다익스트라 알고리즘을 사용하여 최단 경로의 값을 구한다.

2. BFS 알고리즘을 사용하여 최단 경로의 경로를 구한다.

3. BFS 알고리즘으로로 구한 경로를 삭제

4. 다시 한번 다익스트라 알고리즘을 사용해서 거의 최단 경로를 구한다.
   
   
   

1. 다익스트라 알고리즘

from collections import deque
import sys
import heapq
INF = 1e9

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

def bfs():
    q = deque()
    q.append(destination) #반대로 탐색
    while q:
        v = q.popleft()
        if v == start:
            continue 
        for pre_v, pre_c in reversed_graph[v]:
            if distance[pre_v] + graph[pre_v][v] == distance[v]: #목적지에서 최단거리 노드가 선택되면 총 합에서 그 간선의 거리를 뺀 것과 같다
                if (pre_v, v) not in remove_list: #최단거리에 선택된 노드는 삭제
                    remove_list.append((pre_v, v))
                    q.append(pre_v)

while True: #테스트 케이스
    n, m = map(int, sys.stdin.readline().split())
    if n == 0 and m == 0:  # 테스트 케이스 종료
        break
    start, destination = map(int, sys.stdin.readline().split())
    graph = [dict() for _ in range(n)]
    reversed_graph = [[] for _ in range(n)]
    for _ in range(m):
        u, v, p = map(int, sys.stdin.readline().split()) 
        graph[u][v] = p
        reversed_graph[v].append((u, p))  # 경로를 추적하기 위해서 역순 저장

    # 다익스트라 알고리즘을 사용하여 최단 거리 찾기
    distance = [INF] * n
    dijkstra()

    # BFS를 사용하여 최단 경로 추적
    remove_list = list()
    bfs()

    # 최단 경로 제거
    for u, v in remove_list:
        del graph[u][v]

    # 다익스트라 알고리즘을 사용하여 최종 최단 경로 찾기
    distance = [INF] * n
    dijkstra()
    if distance[destination] == INF:  # 거의 최단 경로가 없는 경우
        print(-1)
    else:
        print(distance[destination])

2. C++

#include <stdio.h>
#include <queue>
#include <algorithm>
#include <memory.h>
#define MAX 501
#define TMAX 10001
#define INF 100000000
using namespace std;

int N, K, S, D;
struct st { int to, d; };
struct st2 { int from, to, d; };

bool operator<(st a, st b)
{
    return a.d > b.d;
}
priority_queue<st> pq;
vector<st> t[MAX], t2[MAX];
int d[MAX];
st2 v[TMAX]; // from,to저장
int k[MAX][MAX],  visit[MAX];
int main()
{
#ifdef _DEBUG
    freopen("c:\\study\\b5719.txt", "r", stdin);
#endif
    while (1)
    {
        scanf("%d%d", &N, &K);
        if (N == 0 && K == 0) break;
        scanf("%d%d", &S, &D);
        for (int i = 0; i < N; i++)
            t[i].clear(), t2[i].clear();
        for (int i = 0, a, b, c; i < K; i++)
            scanf("%d%d%d", &a, &b, &c),
            t[a].push_back({ b,c }), t2[b].push_back({ a,c }),
            v[i] = { a,b,c };

        pq.push({ S,0 });
        memset(d, 0x3f, sizeof(d));
        while (!pq.empty())
        {
            st n = pq.top(); pq.pop();
            for (st next : t[n.to])
            {
                if (d[next.to] > n.d + next.d)
                {
                    d[next.to] = n.d + next.d;
                    pq.push({ next.to, n.d + next.d });
                }
            }
        }
        if (d[D] == d[MAX - 1])
        {
            printf("-1\n");
            continue;
        }
        // bfs로 최단경로 제외하고 경로 재설정
        d[S] = 0;
        queue<int> q;
        q.push(D);
        int cnt = 0;
        memset(k, 0, sizeof(k));
        memset(visit, 0, sizeof(visit));
        while (!q.empty())
        {
            int node = q.front(); q.pop();
            if (visit[node]) continue;
            visit[node] = 1;
            for (st next : t2[node])
                if (d[next.to] + next.d == d[node])
                    q.push(next.to),
                    k[next.to][node] = 1; // 최단경로 저장
        }
        for (int i = 0; i < N; i++)
            t[i].clear();
        for (int i = 0; i < K; i++) // 거의최단경로 저장
            if (k[v[i].from][v[i].to] == 0)
                t[v[i].from].push_back({ v[i].to, v[i].d });

        // 다시 다익스트라 돌림
        pq.push({ S,0 });
        memset(d, 0x3f, sizeof(d));
        while (!pq.empty())
        {
            st n = pq.top(); pq.pop();
            for (st next : t[n.to])
            {
                if (d[next.to] > n.d + next.d)
                {
                    d[next.to] = n.d + next.d;
                    pq.push({ next.to, n.d + next.d });
                }
            }
        }
        if (d[D] == d[MAX - 1])
            printf("-1\n");
        else
            printf("%d\n", d[D]);
    }
}