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

문제 링크 : [백준]거의 최단 경로(5719)

5719번: 거의 최단 경로

문제 설명

N개의 도시가 있고, M개의 도로 정보가 주어집니다.

이때, 시작점부터 도착점까지 가는 최단거리를 구성하는 모든 도로를 제외한 도로들을 가지고 최단거리를 구하세요.

입력

N(도시의 수, 1 <= N <= 500)

M(도로의 수, 1 <= M <= 1,000)

S E(시작 도시, 도착 도시)

X_i Y_i C_i(연결 된 도시와 도로의 비용)

7 9
0 6
0 1 1
0 2 1
0 3 2
0 4 3
1 5 2
2 6 4
3 6 2
4 6 4
5 6 1
4 6
0 2
0 1 1
1 2 1
1 3 1
3 2 1
2 0 3
3 0 2
6 8
0 1
0 1 1
0 2 2
0 3 3
2 5 3
3 4 2
4 1 1
5 1 1
3 0 1
0 0

 

출력

5
-1
6

 

카테고리

#다익스트라 #BFS

 

시간 복잡도 상한

O(M²)

 

해결 방법

1. 최단 거리를 구하고, 그 최단거리를 구성하는 도로 정보들을 파악해야 합니다.
2. 그리고 그 도로들을 제외한 도로들을 가지고 다시 최단 거리를 구해야 합니다.
3. 두 지점간의 최단 거리를 구하기 때문에 다익스트라를 이용하여 O(MlogM)의 시간에 최단거리를 구할 수 있습니다.
4. 다음으로 최단 거리를 구성하는 도로 정보를 구합니다.
5. 시작지점S에서 중간지점M까지 거리 + 중간지점M에서 도착지점E까지의 거리 = 시작지점S에서 도착지점E까지의 거리 라는 식이 성립된다면, 두 부분 경로는 최단 경로의 일부가 됩니다.
6. 위 성질을 이용하여, S에서 M(E와 인접한 도시)까지의 거리 + M에서 E까지의 거리가 S에서 E까지의 최단 거리와 같은 경우, 그 엣지가 최단 경로를 이루는 경로이기 때문에, 거의 최단 경로를 구할 때 대상에서 제외합니다.
7. 이런 식으로 반복적용하여 시작지점까지 반복합니다.
8. 제외된 간선들을 제외하고 다시 다익스트라를 사용하여 거의 최단 경로를 구합니다.

시간복잡도

O(MlogM)

코드

#include<cstdio>
#include<string.h>
#include<vector>
#include<queue>
#define pii pair<int,int>
#define mp make_pair
#define INF 999999999
using namespace std;
int n,m,s,e,x,y,z,i,d[500];
bool o[500][500];
vector<pii>v[500],w[500];
priority_queue<pii>q;
queue<pii>p;
void D(){
    q.push(mp(0,s));
    while(!q.empty()){
        pii c=q.top();q.pop();
        if(d[c.second]<INF)continue;
        d[c.second]=-c.first;
        for(pii a:v[c.second])if(!o[c.second][a.second]&&d[a.second]==INF)q.push(mp(c.first+a.first,a.second));
    }
}
int main(){
    while(1){
        scanf("%d%d",&n,&m);
        if(!n)break;
        memset(o,0,sizeof(o));
        for(i=0;i<500;i++)v[i].clear(),w[i].clear(),d[i]=INF;
        scanf("%d%d",&s,&e);
        while(m--){
            scanf("%d%d%d",&x,&y,&z);
            v[x].push_back(mp(-z,y));
            w[y].push_back(mp(z,x));
        }
        D();
        p.push(mp(0,e));
        while(!p.empty()){
            pii c=p.front();p.pop();
            for(pii a:w[c.second]){
                if(!o[a.second][c.second]&&d[a.second]+a.first+c.first==d[e]){
                    o[a.second][c.second]=1;
                    p.push(mp(c.first+a.first,a.second));
                }
            }
        }
        for(i=0;i<500;i++)d[i]=INF;
        D();
        printf("%d\n",d[e]==INF?-1:d[e]);
    }
}