(C++) 백준 1504 특정한 최단 경로 (Dijkstra)

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

1부터 특정 노드(v1, v2)를 거쳐 N까지 가는 최소 경로를 구하는 문제.
dist[x][i] = 노드 x가 노드 i로 가는 최소 거리 라고 정의하고

• 1에서 다른 노드들로 가는 최소 거리
• v1에서 다른 노드들로 가는 최소 거리
• v2에서 다른 노드들로 가는 최소 거리

세가지를 구해서 1 → v1 → v2 →N 으로 가는 값과 1 → v2 → v1 → N 값 중 최소값을 답으로 처리하면 된다.

갈수없는 경우 예외처리 해야함 ㅠ

#include <iostream>
#include <vector>
#include <queue>
using namespace std;


int N, E;
int a,b,c;
vector<pair<int,int>> v[801];
int dist[801][801];
int v1,v2;
priority_queue<pair<int, int>> pq;
const int INF = 800001;

void findShortsPath(int x){

    priority_queue<pair<int, int>> pq;
    pq.push({x,0});
    dist[x][x]=0;

    while(!pq.empty()){

        int now = pq.top().first;
        int distance = pq.top().second;
        pq.pop();

        for(int i=0; i<v[now].size(); i++){

            int next = v[now][i].first;
            int next_distance = distance + v[now][i].second;

            if(dist[x][next]>next_distance){
                dist[x][next] = next_distance;
                pq.push({next, next_distance});
            }
        }
    }

}



int main(){

    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin>>N>>E;

    for(int i=0; i<=N; i++) for(int j=0; j<=N; j++) dist[i][j]=INF;

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


    findShortsPath(1);
    findShortsPath(v1);
    findShortsPath(v2);


    int ans=-1;

    if(dist[1][v1]!=INF && dist[v1][v2]!=INF && dist[v2][N]!= INF) 
    ans=dist[1][v1]+dist[v1][v2]+dist[v2][N];
    if(dist[1][v2]!=INF && dist[v2][v1]!=INF && dist[v1][N]!= INF) 
    ans= min(ans, dist[1][v2]+dist[v2][v1]+dist[v1][N]);

    cout<<ans;

}