[C++] 특정한 최단 경로

백준 1504번

 

다익스트라를 응용한 문제였다

최단 경로는 경로인데 특정한 두 지점을 꼭 지나간 최단 경로 찾기

따라서 최단 경로를 저장하는 배열을 한 지점만 들른 경우, 두 지점 모두 들른 경우 나누어서 만들어주었다

예전에 비슷한 문제를 푼 적 있어서 dist 배열을 다차원 배열로 status 별로 나누는 것은 금방했지만 조건 체크에서 실수를 해서 몇번 틀렸다

꼭 들러야하는 점이 1인 경우 시작점이 1이라 자동적으로 들르게되지만 처음의 코드에서는 해당 케이스를 잡지 못했다

start status를 만들어 시작점이 1인 경우를 따로 체크해주었더니 정답처리되었다

 

최단 경로를 상황별로 나누어 저장하는 것과 시작점이 특정 지점인 경우만 체크해주면 될 듯한 문제!

 

#include <stdio.h>
#include <limits.h>
#include <vector>
#include <queue>
 
using namespace std;
 
vector<pair<int,int> > graph[801]; // [from] to, dist
int dist[801][4]; // not visited, only visited v1, only visited v2, visited both
priority_queue<pair<pair<int,int> ,int> > pq; // ((dist*-1, pos), status) 
// status == 0 not visited
// status == 1 only visited v1
// status == 2 only visited v2
// status == 3 visited both
 
int main(){
    int N,E;
    scanf("%d %d",&N,&E);
    for(int i = 0 ; i < E ; i++){
        int a,b,c;
        scanf("%d %d %d",&a,&b,&c);
        graph[a].push_back(make_pair(b,c));
        graph[b].push_back(make_pair(a,c));
    }
 
    int v1,v2,start_status=0;
    scanf("%d %d",&v1,&v2);
    if(v1==1) start_status=1;
    else if(v2==1) start_status=2;
 
    for(int i = 1 ; i <= N ; i++){
        for(int j = 0 ; j < 4 ; j++){
            dist[i][j] = INT_MAX;
        }
    }
 
    dist[1][0] = 0;
    pq.push(make_pair(make_pair(0,1),start_status));
 
    while(!pq.empty()){
        int distance = pq.top().first.first*-1;
        int now = pq.top().first.second;
        int stat = pq.top().second;
        pq.pop();
        if(stat==3 && now == N){
            printf("%d\n",distance);
            return 0;
        }
 
        for(int i = 0 ; i < graph[now].size() ; i++){
            int next = graph[now][i].first;
            int d = graph[now][i].second;
            int next_stat = stat;
 
            if(next==v1 && stat==0) next_stat = 1;
            else if(next==v1 && stat==2) next_stat = 3;
            else if(next==v2 && stat==0) next_stat = 2;
            else if(next==v2 && stat==1) next_stat = 3;
 
            if(dist[next][next_stat]>distance+d){
                dist[next][next_stat] = distance+d;
                pq.push(make_pair(make_pair(dist[next][next_stat]*-1,next),next_stat));
            }
        }   
    }
    printf("-1\n");
}