백준 1504:특정한 최단 경로

이번문제는 다익스트라 문제예요.. 하지만 주어진 두점을 지나야 해요! 제가 생각한 풀이법은 이렇습니다.

1. 두 점중에서 시작점과 가까운 거리를 구합니다!

2. 두 점중에서 도착점과 가까운 거리를 구합니다!

3. 두 점의 거리를 더해줍니다.

*그리고 만약 첫번째 점을 시작점과 연결했다면 끝나는 점은 다른 한점과 연결해야 최소비용으로 지나갈 수 있겠죠? 교차해서 지나가야 한번씩 방문하면서 최소비용이 나와요!

->이렇게하면 '시작점 ~ (두 점중 택1) ~ (나머지 점) ~ 도착점'의 최단거리가 나올 것 같아요!

그러므로 주어진 두 점에서 다익스트라알고리즘을 돌리면 최단거리가 나오겠죠?

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
#define INF 1e8
 
int main(void) {
    ios::sync_with_stdio(false);
    int N, E; cin >> N >> E;
    vector<vector<pair<int, int>>> graph(N + 1);
    for (int i = 0; i < E; i++) {
        int a, b, c; cin >> a >> b >> c;
        graph[a].push_back(pair<int, int>(b, c));
        graph[b].push_back(pair<int, int>(a, c));
    }
 
    int pass[2]; cin >> pass[0] >> pass[1];//지나야할 두 점이요
    int start[2], mid, end[2];//시작점에서 두점, 두점사이의 거리, 두점에서 도착점
    for (int k = 0; k < 2; k++) {//pass점에 대해서 다익스트라 2번!
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
        vector<bool> visited(N + 1, false);
        vector<int> cost(N + 1, INF);
 
        pq.push(pair<int, int>(0, pass[k]));
        cost[pass[k]] = 0;//pass[k]에서 시작
 
        while (!pq.empty()) {
            int cur;
            do {
                cur = pq.top().second; pq.pop();
            } while (!pq.empty() && visited[cur]);
 
            if (visited[cur]) break;
            visited[cur] = true;
 
            for (auto& i : graph[cur]) {
                int next = i.first; int distance = i.second;
                if (cost[next] > cost[cur] + distance) {
                    cost[next] = cost[cur] + distance;
                    pq.push(pair<int, int>(cost[next], next));
                }
            }
        }
 
        start[k] = cost[1];//각 점에서 시작점까지 비용
        end[k] = cost[N];//각 점에서 도착점까지 비용
        mid = cost[pass[0]];//중간 두 점의 거리
    }
 
    int result = mid + min(start[0] + end[1], start[1] + end[0]);
    //시작점과 도착점의 거리를 더할때 교차해서 더해주어야 각점을 한번씩순회해서 최소비용이 나와요
    if (result <= INF) cout << result << '\n';
    else cout << "-1\n";
 
    return 0;
}