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

문제 링크입니다. https://www.acmicpc.net/problem/9370

9370번: 미확인 도착지

 생각이 필요한 다익스트라 문제였습니다.

목적지 후보지와 출발점, 듀오가 이동한 정점 2개가 주어졌을 때, 어떤 후보지에 향하고 있었는지를 구하는 문제입니다.

 

이 문제를 풀기 위해서는 S-G or G-S 간선을 이동했는지를 구하는 것이 핵심입니다.

출발점에서 목적지 후보지까지 각각 이동한 간선들을 모두 저장하는 것도 방법이지만, S, G정점 활용해 최소 비용을 비교하는 것이 효율적입니다.

 

S-G 간선을 이용했다면, 출발점에서 목적지까지 최소 비용이 출발점 -> S or G -> 후보지의 비용과 같을 것입니다.

 

따라서, 다익스트라 알고리즘을 3번 돌려, 출발지에서 정점까지, S점에서 정점까지, G점에서 정점까지의 최소비용을 전부 구해줍니다.

 

1. 출발점 -> S + S -> G + G -> 후보지

2. 출발점 -> G + G -> S + S -> 후보지

 

2개의 값이, 출발점 -> 후보지의 값과 같으면 해당 후보지를 가고 있는 것입니다.

 

코드에서, Distance 배열이 있는데,

Distance[0][x] = 출발점에서  X점까지의 최소 비용

Distance[1][x] = S에서  X점까지의 최소 비용

Distance[2][x] = G에서  X점까지의 최소 비용 입니다.

 

 

자세한 것은 코드를 참고해주세요

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cmath>
#define P pair<int, int>
#define PP pair<P, int>
#define F first
#define S second
#define INF 987654321

using namespace std;

int test_case;
int N, M, T;
int S, G, H;
vector<P> connect[2001];
vector<int> fin;
int Distance[3][2001];

void reset_distance(){
    for(int i = 0; i < 3; i++){
        for(int j = 1; j <= N; j++){
            Distance[i][j] = INF;
        }
    }
}

void Dijstra(int X, int y){
    priority_queue<P> q;
    q.push({-0, X});
    Distance[y][X] = 0;
    while(!q.empty()){
        int x = q.top().S;
        int cost = -q.top().F;
        q.pop();
        if(Distance[y][x] < cost) continue;
        for(int i = 0; i < connect[x].size(); i++){
            int xx = connect[x][i].F;
            int n_cost = connect[x][i].S + cost;
            if(Distance[y][xx] > n_cost){
                Distance[y][xx] = n_cost;
                q.push({-n_cost, xx});
            }
        }
    }
}

void solve(){
    sort(fin.begin(), fin.end());
    reset_distance();
    Dijstra(S, 0);
    Dijstra(G, 1);
    Dijstra(H, 2);
    for(int i = 0; i < fin.size(); i++){
        int cost_1 = Distance[0][G] + Distance[1][H] + Distance[2][fin[i]];
        int cost_2 = Distance[0][H] + Distance[2][G] + Distance[1][fin[i]];
        int real_cost = Distance[0][fin[i]];
        if(real_cost == cost_1 || real_cost == cost_2){
            cout << fin[i] << " ";
        }
    }
    cout << "\n";
    for(int i = 1; i <= N; i++) connect[i].clear();
    fin.clear();
}

int main() {
    cin.tie(0);
    cout.tie(0);
    cin >> test_case;
    for(int i = 0; i < test_case; i++){
        cin >> N >> M >> T;
        cin >> S >> G >> H;
        for(int j = 1; j <= M; j++){
            int x, y, cost;
            cin >> x >> y >> cost;
            connect[x].push_back({y, cost});
            connect[y].push_back({x, cost});
        }
        for(int j = 1; j <= T; j++){
            int x;
            cin >> x;
            fin.push_back(x);
        }
        solve();
    }
    
    return 0;
}

 

 

질문 및 조언은 댓글을 남겨주세요!