백준 5719번 거의 최단 경로

백준 5719번 거의 최단 경로

#include <iostream>
#include<vector>
#include<queue>
#include<string>
#include<algorithm>
#include<cstring>    
using namespace std;
#define MAX 500+50
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF =987654321;
 
vector<int> parent[MAX];
int adj[MAX][MAX];
int N, M;
int S, D;
int dijkstra(int start) {
    int dist[MAX];
    bool visited[MAX] = {};
    fill(dist, dist + MAX, INF);
    dist[start] = 0;
    for (int k = 0; k < N; k++) {
        int here = N;
        for (int i = 0; i <N; i++) {
            if ( (dist[i] < dist[here])&& !visited[i]) {
                here = i;
            }
        }
        visited[here] = 1;
        for (int j = 0; j < N; j++) {
            int newDist = dist[here] + adj[here][j];
            //최단경로가 여러 개인 경우 구현 방법
            if (newDist < dist[j])            
                parent[j].clear();
            if (newDist <=dist[j]) {
                dist[j] = newDist;
                parent[j].push_back(here);
            }    
        }
    }
    return dist[D]; //목적지의 최단경로 값 반환.
}
// int pos의 pos값을 목적지로 넣어 주면 목적지까지의최단경로 루트가 다지워짐.
void Erase(int pos){
    for (int i : parent[pos]) {
        adj[i][pos] = INF;
        Erase(i);
    }
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    while (1) {
 
        for (int i = 0; i < MAX; i++)
            parent[i].clear();
        fill(&adj[0][0], &adj[MAX-1][MAX-1] + 1, INF);
        cin >> N >> M;
        if (N == 0 && M == 0) break;
        cin >> S >> D;
        for (int i = 0; i < M; i++) {
            int a, b, c;
            cin >> a >> b >> c;
            adj[a][b] = c;
        }
        dijkstra(S);//최단경로 찾고
        Erase(D);    //최단경로로 가는길 모두 지워줌
        int ans = dijkstra(S);    //거의 최단경로 ans 
        if (ans >= INF)            //경로가없는 경우
            cout << -1<<endl;
        else
            cout << ans << endl;
    }
    return 0;
}

출처:https://www.acmicpc.net/problem/5719

최단 경로가 여러가지인 경우. parent배열을 벡터로 구현 하는 방법이 사용되었습니다.

또한 dijkstra함수 안에서 구현 방법이 조금 다르게 변형해주어야 합니다.

이 구현 방법만 배우게 되면, 다양하게 적용할 수 있을 것 같습니다.

유익한 문제였습니다.