[백준] 5719 - 거의 최단 경로 (c++)

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

 

문제 요약

방향 그래프가 주어진다. 시작점과 도착점이 주어질 때 모든 최단 경로에 속하는 간선을 하나도 사용하지 않은 경로 중 최단경로의 길이를 구해라. 

 

풀이 (MlogN)

• 다익스트라

다익스트라를 한 번 돌리면서 한 정점에 대해 최단경로로 도달할 수 있는 전 정점들을 연결하는 그래프를 구성해준다. 보통 다익스트라는 새로운 비용이 원래 비용보다 작을 때만 pq에 추가해주는데 같을 때도 추가해주면 된다. vis배열을 만들어 한 정점 대해 업데이트는 한 번만 되게 한다. 

그렇게 구성한 그래프에서 d부터 s까지 역추적 해가며 포함되는 간선을 모두 지우면 s->d 최단경로의 속하는 간선을 모두 지울 수 있다.

다익스트라 한 번 더 돌려주면 끝

#include <bits/stdc++.h>
using namespace std;
#define ll long long

int main() {
    cin.tie(0)->sync_with_stdio(0);
    while(1) {
        int n,m,s,t;
        cin>>n>>m;
        if(n==0)
            break;
        cin>>s>>t;
        vector<vector<int>> adj(n,vector<int>(n));
        for(int i=0,u,v,c;i<m;i++)
            cin>>u>>v>>c,adj[u][v]=c;
        vector<bool> vis(n);
        priority_queue<array<int,3>,vector<array<int,3>>,greater<array<int,3>>> pq;
        vector<int> dis(n,1e9);
        vector<vector<int>> in(n);
        pq.push({dis[s]=0,s,s});
        while(pq.size()) {
            auto[cc,u,p]=pq.top();pq.pop();
            if(cc>dis[u])continue;
            in[u].push_back(p);
            if(vis[u])continue;
            vis[u]=1;
            for(int v=0;v<n;v++) {
                int c;
                if(!(c=adj[u][v]))continue;
                if(cc+c<=dis[v])
                    pq.push({dis[v]=cc+c,v,u});
            }
        }
        fill(vis.begin(),vis.end(),0);
        queue<int> q;
        q.push(t);
        while(q.size()) {
            int u=q.front();q.pop();
            for(int v:in[u]) {   
                adj[v][u]=0;
                if(!vis[v])
                    q.push(v),vis[v]=1;
            }
        }
        fill(dis.begin(),dis.end(),1e9);
        pq.push({dis[s]=0,s,0});
        while(pq.size()) {
            auto[cc,u,p]=pq.top();pq.pop();
            if(cc>dis[u])continue;
            for(int v=0;v<n;v++) {
                int c;
                if(!(c=adj[u][v]))continue;
                if(cc+c<dis[v])
                    pq.push({dis[v]=cc+c,v,u});
            }
        }
        cout<<(dis[t]==1e9?-1:dis[t])<<'\n';
    }
}