9370번: 미확인 도착지

문제 링크

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

9370번: 미확인 도착지

 

 

문제 풀이 코드

#include <queue>
#include <vector>
#include <iostream>
#include <algorithm>
#include <functional>

using namespace std;
using P = pair<int,int>;

const int INF=987654321;
const int MN=2001;

vector <P> graph[MN];

vector <int> Dijkstra(int N, int S){

    vector <int> Dijk(N+1,INF);

    priority_queue <P, vector <P>, greater<P>> pq;

    Dijk[S]=0;
    pq.push({0,S});

    while(!pq.empty()){

        P cur = pq.top(); pq.pop();
        int cur_w=cur.first;
        int cur_v=cur.second;

        if(Dijk[cur_v]<cur_w) continue;

        for(int j=0; j<graph[cur_v].size(); j++){
            
            int next_w=graph[cur_v][j].first;
            int next_v=graph[cur_v][j].second;

            if(Dijk[next_v]>cur_w+next_w){

                Dijk[next_v]=cur_w+next_w;
                pq.push({Dijk[next_v],next_v});

            }
        }
    }

    return Dijk;
}

int main(void){

    int T; cin>>T;

    while(T--){//테스트 케이스만큼

        //graph 초기화
        for(int i=0; i<MN; i++) {
            
                graph[i].clear();
            
        }
                
        int n,m,t; cin>>n>>m>>t;
        int s,g,h; cin>>s>>g>>h;

        for(int i=0; i<m; i++){
            int u,v,w; cin>>u>>v>>w;
            graph[u].push_back({w,v});
            graph[v].push_back({w,u});
        }

        //목적지 후보 입력 받기
        vector <int> dest;
        
        for(int i=0; i<t; i++){
            int v; cin>>v;
            dest.push_back(v);
        }

        vector <int> answer;

        for(int i=0; i<t; i++){

            vector <int> dijk_s=Dijkstra(n,s);
            vector <int> dijk_g=Dijkstra(n,g);
            vector <int> dijk_h=Dijkstra(n,h);

            if(dijk_s[dest[i]]==dijk_s[g]+dijk_g[h]+dijk_h[dest[i]]){
                answer.push_back(dest[i]);
            }
            else if(dijk_s[dest[i]]==dijk_s[h]+dijk_h[g]+dijk_g[dest[i]]){
                answer.push_back(dest[i]);
            }

        }

        sort(answer.begin(), answer.end());

        for(int i=0; i<answer.size(); i++){
            cout<<answer[i]<<' ';
        }cout<<'\n';

    }

    return 0;

}

 

이 문제... 증맬로 어려웠다.

교차로인 정점도 지나쳐야하고, 정답 후보가 될 정점도 추려내야했다. 

 

일딴 교차로를 지나는 최단 경로를 구하기 위해서는 앞서 풀었던

백준 1504번 특정한 최단 경로 의 문제 풀이 방식을 활용했다.

 

g와 h가 경유지이고 목적지는 앞서 입력 받은 목적지 후보(dest) 중 하나가 된다.

경우의 수는 아래와 같이 두 가지로 나뉜다.

 

 - s(시작정점) -> g-> h-> dest[i](목적지 후보)

 - s(시작정점) -> h-> g-> dest[i](목적지 후보)

 

위의 두 가지의 경우 최단경로 값이 시작정점부터 목적지 후보까지의 최단경로 값과 같다면 정답이다. 

if(dijk_s[dest[i]]==dijk_s[g]+dijk_g[h]+dijk_h[dest[i]]) answer.push_back(dest[i]);
else if(dijk_s[dest[i]]==dijk_s[h]+dijk_h[g]+dijk_g[dest[i]]) answer.push_back(dest[i]);

아마도 이 부분이 이문제의 핵심 풀이 부분이 될 것이다.

 

머리를 굴리자 머리를!