[백준]특정한 최단 경로(1504)

문제 링크 : [백준]특정한 최단 경로(1504)

1504번: 특정한 최단 경로

 

문제 설명

1번 노드에서 N번노드까지 가는데 특정한 두 노드를 거쳐서 가는 최단 거리를 구하세요.

입력

N(노드의 갯수, 1 <= N <= 800)

M(간선의 갯수, 1 <= M <= 200,000)

A_i B_i C_i(간선의 정보)

V1, V2(경유지 노드)

4 6
1 2 3
2 3 3
3 4 1
1 3 5
2 4 5
1 4 4
2 3

 

출력

7

 

카테고리

#다익스트라

 

시간 복잡도 상한

O(NlogN) 혹은 O(MlogM)

 

해결 방법

1. 두 점 사이의 최단거리이므로 다익스트라를 생각해봅니다.
2. 그러나 중간의 두 점을 경유해야 합니다.
3. 그렇다는 것은 시작점->V1->V2->도착점, 혹은 시작점->V2->V1->도착점 두 가지 중 하나의 경우 일 것입니다.
4. 시작점을 기준으로 다익스트라를 돌리게 되면, 시작점에서 V1, V2, 도착점 까지의 최단 거리를 구할 수 있습니다.
5. 마찬가지로, V1, V2를 기준으로 돌리면 각 노드를 시작점으로 하여 다른 모든 노드까지의 최단 거리를 구할 수 있습니다.
6. 4, 5에서 구한 정보를 가지고, 아래 두 가지 중 최소 비용을 구하면 됩니다.
   1. (시작점 -> V1) + (V1  -> V2) + (V2 -> 도착점)
   2. (시작점 -> V2) + (V2 -> V1) + (V1 -> 도착점)
7. 단, V1과 V2가 시작점이나 도착점 일 수도 있으니, 그 점만 유의하시면 됩니다.

시간복잡도

O(N+MlogM)

코드

#include<cstdio>
#include<vector>
#include<queue>
#include<string.h>
using namespace std;
typedef pair<int,int> p;
int n,m,s[3][801],i,j,x,y,a,b,c,d[3]={1};
vector<p>v[801];
priority_queue<p,vector<p>,greater<p>>q;
int g(int a,int b){return a>b?b:a;}
int main(){
    scanf("%d%d",&n,&m);
    memset(s,0xff,sizeof(s));
    while(m--){
        scanf("%d%d%d",&a,&b,&c);
        v[a].push_back({c,b});
        v[b].push_back({c,a});
    }
    scanf("%d%d",d+1,d+2);
    for(j=0;j<3;j++){
        q.push({0,d[j]});
        while(!q.empty()){
            p z=q.top();q.pop();
            if(s[j][z.second]>0)continue;
            s[j][z.second]=z.first;
            for(i=0;i<v[z.second].size();i++){
                p t=v[z.second][i];
                if(s[j][t.second]<0)q.push({z.first+t.first,t.second});
            }
        }
    }
    if(s[0][d[1]]>=0&&s[0][d[2]]>=0&&s[0][n]>=0)
        printf("%d",g(s[0][d[1]]+s[1][d[2]]+s[2][n],s[0][d[2]]+s[2][d[1]]+s[1][n]));
    else printf("-1");
}