[백준][C++] 9370 미확인 도착지

www.acmicpc.net/problem/9370

9370번: 미확인 도착지

 

 

 

알고리즘 종류

    - 다익스트라

 

 

 

사고 과정

    - 아래와 같은 경우로 최단 거리 경로가 나올 수 있다. 그러면 하늘색 화살표마다 다익스트라 알고리즘을 적용한다. 첫 번째 경우로 예를 들면, S->G, H->E (G-H는 도로가 1개이다.)에서 경로들의 합을 구하고, S->E와 비교해서 같으면 된다.

 

    - 그런데 문제는 G와 H 중에 S와 가까운 노드는 무엇인가이다. S시작 다익스트라를 해보면, 2->1 VS 2->3 중에 노드 1까지 거리가 작으므로 가장 가까운 노드는 1이다. 이제 경우 2개에서 1개로 줄었다. 따라서 2->1 경로 비용을 구하고, 3->목적지까지 경로 비용을 구해서 더한 뒤에 2->목적지까지 경로 비용과 비교해서 같으면 우리가 찾는 목적지가 된다.

 

 

 

구현(C++)

#include <iostream>
#include <vector>
#include <cstring>
#include <queue>
#include <algorithm>
#define INF 987654321;
 
using namespace std; 
 
int T;
int n, m, t;
int s, g, h;
int mgCost;
 
vector<vector<pair<int, int> > > edges;
vector<int> dests;
 
int S[2001];
int costs[2001];
 
void dijsktra(int start){
    
    priority_queue<pair<int, int> > pq;
    pq.push({0, start});
    costs[start] = 0;
    
    while(!pq.empty()){
        int here = pq.top().second;
        int cost = -pq.top().first;
        pq.pop();
 
        if(cost > costs[here]) continue;
        for(int i=0; i<edges[here].size(); i++){
            int next = edges[here][i].first;
            int next_cost = cost + edges[here][i].second;
            
            if(next_cost < costs[next]){
                costs[next] = next_cost;
                pq.push({-next_cost, next});
            }
        }
    }
}
 
 
void solution(){
    // 출발점에서 G 또는 H로 이동  
    for(int i=0; i<=n; i++) costs[i] = INF;
    dijsktra(s);
    
    // 시작점과 가장 가까운 교차로 노드 찾기  
    int closeNode, farNode;
    
    if(costs[g] < costs[h]) {
        closeNode = g;
        farNode = h;
    }
    else{
        closeNode = h;
        farNode = g;
    } 
    
    // 출발 -> 최단 거리 경로 중에서 가장 가까운 교차 노드 
    int cost = costs[closeNode] + mgCost;
    
    // 가장 가까운 노드 G/H에서 도착지까지 이동  
    memcpy(S, costs, sizeof(costs));
    for(int i=0; i<=n; i++) costs[i] = INF;
    dijsktra(farNode);
    
    // 시작점 -> 도착점과 시작점 -> G/H -> 도착점 경로를 비교해서 같으면 도착점 넣어주기  
    vector<int> answer;
    for(int i=0; i<dests.size(); i++){
        int e = dests[i];
        if(S[e] == cost + costs[e]){
            answer.push_back(e);
        }
    }
    
    // 출력  
    sort(answer.begin(), answer.end());
    for(int i=0; i<answer.size(); i++) cout << answer[i] << " ";
    cout << endl;
}
 
 
int main(void){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    
    cin >> T;
    while(T--){
        
        cin >> n >> m >> t;
        cin >> s >> g >> h;
        
        edges.clear();
        dests.clear();
        edges.resize(n+1);
        
        int u, v, c;
        for(int i=0; i<m; i++){
            cin >> u >> v >> c;
            edges[u].push_back({v,c});
            edges[v].push_back({u,c});
            
            if(u==g && v==h) mgCost = c;
            else if(u==h && v==g) mgCost = c;
        }
        
        int e;
        for(int i=0; i<t; i++){
            cin >> e;
            dests.push_back(e);
        }
        
        solution();
    }
}

 

 

 

시행착오