백준 5719 / 거의 최단 경로

나중에 다시 한번 풀어야할 문제.

다익스트라와 BFS를 동시에 사용해야하는 문제.

어렵다. 굉장히 헤멘 문제.

플로이드 워셜 알고리즘으로 풀면 최단경로를 '모두' 찾는데 어려움이 생긴다.

1. 다익스트라로 최단경로를 (모두) 찾는다. (최단경로를 따로 저장해두어야한다)

2. 최단경로에 걸친 간선들을 모두 삭제한다.

3. 다익스트라로 새 최단경로를 찾는다.

다익스트라 코드에서 trace를 갱신하는 부분이 핵심이다.

코드

#include<stdio.h>
#include<vector>
#include<iostream>
#include<queue>
 
#define MAX 501;
#define INF 987654321;
 
using namespace std;
 
int n, m;
 
int dijk(int start, int goal, vector<vector<pair<int, int>>>&arr, vector<vector<pair<int, int>>>&trace) {
 
    vector<int>dist(n + 1,987654321);
 
    priority_queue<pair<int, int>>pq;
    pq.push(make_pair(0,start));
    dist[start] = 0;
 
    while (!pq.empty()) {
        int now = pq.top().second;
        int cost = -pq.top().first;
        pq.pop();
 
        for (int i = 0; i < arr[now].size(); i++) {
            int to = arr[now][i].first;
            int c = arr[now][i].second;
 
            if (c == -1)continue;
 
        
 
            if (dist[to] > cost + c) {
                dist[to] = cost + c;
                pq.push(make_pair(-dist[to], to));
 
 
                trace[to].clear();
                trace[to].push_back(make_pair(now, dist[to]));
            }
            if (dist[to] == cost + c) {
                trace[to].push_back(make_pair(now, dist[to]));
            }
        }
    }
    
    return dist[goal];
 
}
void bfs(int goal, vector<vector<pair<int, int>>>&arr, vector<vector<pair<int, int>>>&trace) {
    queue <int > q;
 
    q.push(goal);
    while (!q.empty()) {
        int now = q.front();
        q.pop();
 
        for (int i = 0; i < trace[now].size(); i++) {
            int to = trace[now][i].first;
 
            for (int i = 0; i < arr[to].size(); i++) {
                if (arr[to][i].first == now) {
                    arr[to][i].second = -1;
                }
            }
            q.push(to);
        }
    }
 
}
 
 
int main() {
    //freopen("Text.txt", "r", stdin);
    
    while (1) {
 
        vector<vector<pair<int, int>>>arr;
        vector<vector<pair<int, int>>>trace;
 
        cin >> n >> m;
 
        if (n == 0 && m == 0)break;
        
        int start, goal;
        
        cin >> start >> goal;
 
        arr.resize(n + 1);
        trace.resize(n + 1);
 
        for (int i = 0; i < m; i++) {
            int from, to, cost;
            cin >> from >> to >> cost;
 
            arr[from].push_back(make_pair(to, cost));
        }
 
        dijk(start, goal,arr,trace);
 
        bfs(goal,arr,trace);
 
        if (dijk(start, goal,arr,trace) == 987654321) {
            cout << -1 << endl;
        }
        else cout << dijk(start, goal,arr,trace)<<endl;
 
    }
 
 
 
}