Beakjoon 1504 특정한 최단 경로

03 Mar 2021 in Algorithm

문제 링크 : https://www.acmicpc.net/problem/1504

나의 풀이

정점 1에서 정점 v1과 v2을 지나 정점 N으로 가는 경로는 1->v1->v2->N or 1->v2->v1->N 으로 두 가지가 있다.
이 때 1에서 v1 또는 v2로 가는 경로가 최단이여야하고, v1->N 또는 v2->N도 최단 경로여야 하기 때문에 1에서 모든 정점까지의 최단경로, v1에서 모든 정점까지의 최단경로, v2에서 모든 정점까지의 최단경로를 다익스트라 알고리즘을 통해 구하면 문제를 해결할 수 있다.

풀이 코드 : 1504 특정한 최단 경로

#include <iostream>
#include <vector>
#include <queue>

#define INF 2000000000

using namespace std;

vector<vector<pair<int, int>>> graph;
vector<vector<int>> dist;

void dijkstra(int start, int j){
    priority_queue<pair<int, int>> pq;
    dist[j][start] = 0;
    pq.push(make_pair(0, start));
    while(!pq.empty()){
        int curr = pq.top().second;
        int curr_w = pq.top().first;
        pq.pop();
        if(dist[j][curr] < curr_w) continue;

        for(int i=0;i<graph[curr].size();i++){
            int next = graph[curr][i].second;
            int w = graph[curr][i].first;
            if(dist[j][next] > dist[j][curr] + w){
                dist[j][next] = dist[j][curr] + w;
                pq.push(make_pair(-w, next));
            }
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int N, E;
    cin>>N>>E;

    graph.resize(N+1);
    dist.resize(3);
    
    int a,b,c;

    for(int i=0;i<E;i++){
        cin>>a>>b>>c;
        graph[a].push_back(make_pair(c,b));
        graph[b].push_back(make_pair(c,a));
    }

    vector<int> start;
    start.resize(3);
    start[0] = 1;
    cin>>start[1]>>start[2];

    for(int j=0;j<3;j++){
        dist[j].resize(N+1);
        for(int i=1;i<=N;i++){
            dist[j][i] = INF;
        }
        dijkstra(start[j], j);
    }
    int answer = INF;
    if(dist[0][start[1]] != INF && dist[1][start[2]] != INF && dist[2][N] != INF && answer > dist[0][start[1]] + dist[1][start[2]] + dist[2][N]){
        answer = dist[0][start[1]] + dist[1][start[2]] + dist[2][N];
    }
    if(dist[0][start[2]] != INF && dist[2][start[1]] != INF && dist[1][N] != INF && answer > dist[0][start[2]] + dist[2][start[1]] + dist[1][N]){
        answer = dist[0][start[2]] + dist[2][start[1]] + dist[1][N];
    }
    if(answer >= INF || answer < 0) cout<<-1<<"\n";
    else cout<<answer<<"\n";
}

채점결과