거의 최단 거리

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

5719번: 거의 최단 경로

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<utility>
#include<queue>
 
using namespace std;
 
int n, m, start, ending;
int map[501][501];
bool d[501];
bool d2[501];
bool dist[501];
int dos[501]; int dos2[501];
int minn = 987654321;
vector<int>ans;
vector<vector<pair<int,int>>> remov;
 
void bfs() {
    queue<int> q;
    q.push(start);
    dist[start] = true;
    while (!q.empty()) {
        int st = q.front(); q.pop();
        for (int i = 0; i < n; i++) {
            if (map[st][i] != 0 && dist[i] == false) {
                dist[i] = true;
                dos[i] = dos[st] + map[st][i];
                
                q.push(i);
            }
            else if (map[st][i] != 0 && dist[i] == true) {
                if (dos[i] > dos[st] + map[st][i]) {
                    dist[i] = true;
                    dos[i] = dos[st] + map[st][i];
            
                    q.push(i);
                }
            }
        }
    }
}
 
 
void dfs(int x, int y, int cnt, vector<pair<int,int>>& gy) {
    if (cnt > dos[ending]) return;
    if (x == y) {
        if (cnt == dos[ending]) {
            remov.push_back(gy);
        }
        return;
    }
    else {
        for (int i = 0; i < n; i++) {
            if (map[x][i] != 0 && d[i] == false) {
                d[i] = true;
                gy.push_back({ x,i });
                dfs(i, y, cnt + map[x][i],gy);
                d[i] = false;
                gy.pop_back();
            }
        }
    }
}
 
void bfs2() {
    queue<int> q;
    q.push(start);
    d2[start] = true;
    while (!q.empty()) {
        
        int st = q.front(); q.pop();
        for (int i = 0; i < n; i++) {
            if (map[st][i] != 0 && d2[i] == false) {
                d2[i] = true;
                dos2[i] = dos2[st] + map[st][i];
 
                q.push(i);
            }
            else if (map[st][i] != 0 && d2[i] == true) {
                if (dos2[i] > dos2[st] + map[st][i]) {
                    d2[i] = true;
                    dos2[i] = dos2[st] + map[st][i];
                    q.push(i);
                }
            }
        }
    }
    if (dos2[ending] == 0) {
        cout << -1 << '\n';
    }
    else {
        cout << dos2[ending] << '\n';
    }
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    while (true) {
        int minn = 987654321;
 
        cin >> n >> m;
        if (n == 0 && m == 0) {
            return 0;
        }
        cin >> start >> ending;
        for (int i = 0; i < m; i++) {
            int u, v, p;
            cin >> u >> v >> p;
            map[u][v] = p;
 
            
        }
        bfs();
        
        
        ans.clear();
        minn = dos[ending];
        vector<pair<int, int>>gy;
        dfs(start, ending, 0, gy);
        for (int i = 0; i < remov.size(); i++) {
            
            for (int j = 0; j < remov[i].size(); j++) {
                map[remov[i][j].first][remov[i][j].second] = 0;
            }
            
        }
        bfs2();
        int s, y;
        
        memset(map, 0, sizeof(map));
        memset(dos, 0, sizeof(dos));
        memset(dos2, 0, sizeof(dos2));
        memset(d, false, sizeof(d));
        memset(d2, false, sizeof(d2));
        memset(dist, false, sizeof(dist));
        remov.clear();
    }
}
 

나름 어려웠던문제가 아닐까싶다.

하지만 사실 로직자체는 굉장히 간단했다.

BFS로 최단거리 구하고 -> DFS로 최단거리에 해당하는 모든것들 경로를 저장하고 저장된 경로 제거하고

다시 BFS로 최단거리를 구하면 거의 최단 경로를 구할수있게된다.