백준 01504 - 특정한 최단 경로

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

1504번: 특정한 최단 경로

 

고려사항

- 다익스트라 알고리즘 사용

- INF 는 800개의 정점이 직선으로 쭉 연결되었을 때의 최대값인 800 * 200000 + 1

- s -> v1 -> v2 -> e 인 경우와 s -> v2 -> v1 -> e 인 경우를 모두 구해서 작은 값 리턴,

마지막으로 65 - 81 줄과 같이 경로인지 판별해야함. 아닐시 -1 출력

 

깨달은 점

- 모든 정점에서 다른 모든 정점까지의 최단 거리를 구하는 플로이드 워셜 알고리즘을 알고 있음에도,

다익스트라 연습을 위해 일부로 사용했는데 알고보니

n = 800 와 같이 n이 클 시에는 다익스트라 알고리즘이 더 빠르다 ( 당연한 얘기... 플로이드는 n^3)

- 59 - 61 줄과 같이 시작 점의 cost 값은 0으로 초기화 해주자..

 

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <string.h>
#define INF 160000001
using namespace std;

int n, e;
vector<pair<int, int>> vList[801];

int cost[3][801];
int start[3];

void sol(){
    for(int i=0;i<3;++i){
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int,int>>> pq;
        int s = start[i];
        int v, w, eNum, nextV, nextW;

        pq.push({0,s});
        while(!pq.empty()){
            w = pq.top().first;
            v = pq.top().second;
            pq.pop();
            eNum = vList[v].size();

            for(int j=0;j<eNum;++j){
                nextW = vList[v][j].first;
                nextV = vList[v][j].second;

                if(w + nextW < cost[i][nextV]){
                    cost[i][nextV] = w + nextW;
                    pq.push({cost[i][nextV], nextV});
                }
            }
        }
    }

    return;
}

int main() {
    int from, to, w, tmp1, tmp2, ans;
    cin>>n>>e;
    for(int i=0;i<e;++i){
        cin>>from>>to>>w;
        vList[from].push_back({w, to});
        vList[to].push_back({w, from});
    }
    start[0] = 1;
    cin>>start[1]>>start[2];

    for(int i=1;i<=n;++i){
        cost[0][i] = INF;
        cost[1][i] = INF;
        cost[2][i] = INF;
    }
    cost[0][1] = 0;
    cost[1][start[1]] = 0;
    cost[2][start[2]] = 0;

    sol();

    if(cost[0][start[1]] == INF || cost[1][start[2]] == INF || cost[2][n] == INF){
        tmp1 = INF;
    }else{
        tmp1 = cost[0][start[1]]+cost[1][start[2]]+cost[2][n];
    }

    if(cost[0][start[2]] == INF || cost[2][start[1]] == INF || cost[1][n] == INF){
        tmp2 = INF;
    }else{
        tmp2 = cost[0][start[2]]+cost[2][start[1]]+cost[1][n];
    }

    if(tmp1 == INF && tmp2 == INF){
        ans = -1;
    }else{
        ans = min(tmp1, tmp2);
    }

    cout<<ans;
    return 0;
}