미확인 도착지 C++ - 백준 9370

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

최단경로 문제.

문제 접근

이 문제에서 핵심은 최단 거리를 갱신해줄 때 bool 배열 갱신을 어떻게

해주는 것이냐가 관건이었다.

냄새를 맡은 도로와 그 도로로 이어진 도로를 찾기 위해 bool 배열을

사용해 최단 경로가 냄새를 맡은 곳과 이어지면 그 노드를 참으로 바꾸어주었다.

최단 거리가 같은 경우가 여러가지 중복될 수 있으므로 그 경우를 따져주어야 하는데,

만약 최단 거리가 갱신된다면 최단 거리를 갱신시키는 노드가 냄새 맡은 도로에서

왔으면 갱신되는 노드를 참으로,

아니면 거짓으로 체크해준다.

최단 거리가 갱신되지 않으면 갱신되는 노드가 참이었으면 놔두고,

거짓이었을 때는 갱신시키는 노드에 따라 참, 거짓을 체크한다.

이를 제외하고는 일반 다익문제와 동일하다.

코드는 다음과 같다.

#include <bits/stdc++.h>
#define INF 1e9
using namespace std;

void solve(){
    int n,m,t,s,g,h,a,b,dis;
    cin >> n >> m >> t >> s >> g >> h;
    vector<vector<pair<int, int>>> graph(n+1);
    vector<int> des(t),d(n+1,INF);
    vector<bool> ck(n+1,0);
    for(int i=0;i<m;i++){
        cin >> a >> b >> dis;
        graph[a].push_back({b,dis});
        graph[b].push_back({a,dis});
    }
    for(int i=0;i<t;i++) cin >> des[i];
    sort(des.begin(),des.end());
    priority_queue<pair<int, int>,vector<pair<int, int>>, greater<pair<int, int>>> pq;
    d[s]=0; pq.push({0,s});
    while(!pq.empty()){
        int now=pq.top().second;
        int dist=pq.top().first;
        pq.pop();
        for(int i=0;i<graph[now].size();i++){
            int cost=dist+graph[now][i].second;
            if(d[graph[now][i].first]>=cost){
                if(now==g && graph[now][i].first==h) ck[h]=1;
                else if(now==h && graph[now][i].first==g) ck[g]=1;
                else if(ck[now]) ck[graph[now][i].first]=1;
                else if(d[graph[now][i].first]>cost) ck[graph[now][i].first]=0;
                if(d[graph[now][i].first]>cost){
                    d[graph[now][i].first]=cost;
                    pq.push({cost,graph[now][i].first});
                }
            }
        }
    }
    for(int i=0;i<t;i++) if(ck[des[i]]) cout << des[i] << ' ';
    cout << '\n';
    return;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int t; cin >> t;
    while(t--) solve();
    return 0;
}