[C++] 9370번 미확인 도착지 - 그래프 이론, 데이크스트라

1. 문제

• 한 양방향 그래프에서 어떤 예술가 한 쌍이 s지점에서 출발해서 g와 h 교차로 사이 도로를 지나 최단경로로 이동해 어떤 목적지로 도달한다고 할 때 어디로 가고 있을까?

<입력>

• .- 1 -   테스트 케이스의 개수 $T(1\le T\le 100)$
  • - 1 -   $n,m,t(2\le n\le 2,000,1\le m\le 50,000,1\le t\le 100)$
    • 교차로, 도로 목적지 후보의 개수
  • - 2 -   $s,g,h(1\le s,g,h\le n)$
    • s: 예술가의 출발지 $(g\ne h)$
  • - m개의 줄 -   $b,d(1\le a<b\le n,1\le d\le 1,000)$
    • a와 b사이에 길이 d의 양방향 도로가 존재
  • - t개의 줄 -   t개의 목적지 후보들
    • 서로 다르고 s와도 다르다
• 교차로 사이에는 도로가 최대 1개 있다. m개의 줄 중에서 g와 h 사이의 도로를 나타내는 것이 존재하고 이도 최단 거리의 일부이다.

<출력>

• 가능한 목적지를 오름차순으로 출력

2. 재정의

• 그래프가 주어졌을 때 최단 경로중 하나가 주어지면 가능한 목적지를 출력하라.

3. 해결 방법

1. 다익스트라로 주어진 경로가 어느 방향으로 가는지 찾기. 이 경로도 최단 경로에 포함되므로 dist[g] < dist[h]이면 항상 g->h로 간다는 것을 알 수 있음
2. h에서 다익스트라를 사용
3. 첫 번째 최단경로는 dist1[]에, 두 번째 최단경로는 dist2[] 에 저장하고 가능한 후보 dist1[target[]] = dist1[h] + dist2[target[]]이면 가능해서 이를 ans에 추가하고 이를 출력

4. 실수한 점, 개선할 점

• priority_queue를 선언할 때 <int, vector<pii>, greater<pii>>로 하면 onlinegdb c++ compiler에는 돌아가는데 백준에서는 돌아가지 않으므로 <pii, vector<pii>, greater<pii>>로 선언해야 됨

 

<코드>

#include <iostream>
#include <algorithm>
#include <string.h>
#include <vector>
#include <queue>

#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define pii pair<int, int>
#define fi first
#define se second

using namespace std;

const int INF = 987654321;
const int MAX_n = 2001;
const int MAX_t = 101;

// <문제>
// 테스트 케이스의 수 T
int T;
// 교차로, 도로, 목적지 후보의 개수 n, m, t
int n, m, t;
// 예술가들의 출발지 s, g, h
int s, g, h;
// 그래프 adj[]
vector<pii> adj[MAX_n];
// 목적지 후보 target[]
int target[MAX_t];

// 다익스트라 알고리즘으로 구한 최단 거리, g or h를 지난 최단 거리
int dist1[MAX_n], dist2[MAX_n];

// 정답
vector<int> ans;

void input() {
    // 배열 초기화
    for(int i=0; i<MAX_n; i++)
        adj[i].clear();
    memset(target, 0, sizeof target);
    fill(dist1, dist1+MAX_n, INF);
    fill(dist2, dist2+MAX_n, INF);
    ans.clear();
    
    cin >> n >> m >> t;
    cin >> s >> g >> h;
    // 양방향 그래프 만들기
    for(int i=0; i<m; i++) {
        int a, b, d;
        cin >> a >> b >> d;
        adj[a].push_back({b, d});
        adj[b].push_back({a, d});
    }
    for(int i=0; i<t; i++)
        cin >> target[i];
}

void Dijkstra(int S, int dist[MAX_n]) {
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    // 처음 위치
    pq.push({0, S});
    dist[S] = 0;
    
    while(!pq.empty()) {
        // 우선순위 큐에서 가장 낮은 가중치를 가진 곳에서 빼오기
        int Cur = pq.top().se;
        pq.pop();
        
        for(auto x : adj[Cur]) {
            // 다음 노드
            int Next = x.fi;
            // 간선의 가중치
            int NCost = x.se;
            
            //cout << Cur << ' ' << Next << ' ' << NCost << '\n';
            
            // 이 길의 가중치 합이 작다면 갱신하기
            if(dist[Next] > NCost + dist[Cur]) {
                dist[Next] = NCost + dist[Cur];
                pq.push({dist[Next], Next});
            }
        }
    }
}

void solve() {
    input();

    // s에서 출발했을 때 얻을 수 있는 최단 거리
    Dijkstra(s, dist1);
    if(dist1[g] > dist1[h])
        swap(g, h);
    // h에서 출발했을 때 얻을 수 있는 최단 거리
    Dijkstra(h, dist2);
    // g에서 목적지 까지의 거리와 s에서 목적지까지의 거리가 같으면 가능
    for(int i=0; i<t; i++) {
        int tg = target[i];
        if(dist1[tg] == dist2[tg] + dist1[h])
            ans.push_back(tg);
    }
    // ans 오름차순 정렬하기
    sort(ans.begin(), ans.end());
    
    for(auto x : ans)
        cout << x << ' ';
    cout << '\n';
    
    /*
    for(int i=0; i<n; i++)
        cout << i << ' ' << dist1[i] << ' ' << dist2[i] << '\n';
    */
}

int main() {
    fastio;
    
    cin >> T;
    while(T--)
        solve();
    
    return 0;
}

 

 

※현재 고등학교 등교 중인 학생입니다. 이제 알고리즘을 본격적으로 공부하기 시작해서 아직 초보입니다. 혹시 제가 잘못 알고 있는 점이나 더 좋은 풀이 방법이 있어 댓글에 남겨주시면 감사히 하나하나 열심히 읽어보겠습니다. 좋아요, 단순한 댓글 한마디라도 저에겐 큰 힘이 됩니다! 감사합니다.