[백준] 9370번 미확인 도착지

9370 미확인 도착지

문제

---

(취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 출발했다는 것, 그리고 목적지 후보들 중 하나가 그들의 목적지라는 것이다. 그들이 급한 상황이기 때문에 목적지까지 우회하지 않고 최단거리로 갈 것이라 확신한다. 이상이다. (취익)

어휴! (요란한 옷차림을 했을지도 모를) 듀오가 어디에도 보이지 않는다. 다행히도 당신은 후각이 개만큼 뛰어나다. 이 후각으로 그들이 g와 h 교차로 사이에 있는 도로를 지나갔다는 것을 알아냈다. 이 듀오는 대체 어디로 가고 있는 것일까?

입력

---

첫 번째 줄에는 테스트 케이스의 T(1 ≤ T ≤ 100)가 주어진다. 각 테스트 케이스마다

• 첫 번째 줄에 3개의 정수 n, m, t (2 ≤ n ≤ 2 000, 1 ≤ m ≤ 50 000 and 1 ≤ t ≤ 100)가 주어진다. 각각 교차로, 도로, 목적지 후보의 개수이다.
• 두 번째 줄에 3개의 정수 s, g, h (1 ≤ s, g, h ≤ n)가 주어진다. s는 예술가들의 출발지이고, g, h는 문제 설명에 나와 있다. (g ≠ h)
• 그 다음 m개의 각 줄마다 3개의 정수 a, b, d (1 ≤ a < b ≤ n and 1 ≤ d ≤ 1 000)가 주어진다. a와 b 사이에 길이 d의 양방향 도로가 있다는 뜻이다.
• 그 다음 t개의 각 줄마다 정수 x가 주어지는데, t개의 목적지 후보들을 의미한다. 이 t개의 지점들은 서로 다른 위치이며 모두 s와 같지 않다.

교차로 사이에는 도로가 많아봐야 1개이다. m개의 줄 중에서 g와 h 사이의 도로를 나타낸 것이 존재한다. 또한 이 도로는 목적지 후보들 중 적어도 1개로 향하는 최단 경로의 일부이다.

출력

---

테스트 케이스마다 입력에서 주어진 목적지 후보들 중 불가능한 경우들을 제외한 목적지들을 공백으로 분리시킨 오름차순의 정수들로 출력한다.

---

풀이)

Dijkstra algorithm을 이용해서 푼 문제이다.

g-h도로가 목적지 후보로 향하는 최단경로의 일부임을 잘 생각하고 풀면 된다.

풀이과정은 이러하다.

1. g랑 h을 지나는 길만 홀수 값으로 두고, 나머지 길들은 짝수 값으로 둔다. -> g-h길을 지났는지 이후에 확인하기위해

   짝수값으로 두는 방법은 *2 씩하면 된다 (홀수*2 = 짝수, 짝수*2 = 짝수 성질 이용)

2. 출발지 s에서 각 모든 교차로까지의 최단 경로 길이를 구한다.(Dijkstra 이용)

3. 각 목적지까지 경로 길이가 INF이면 길이 없어서 못갔다는 뜻이고, 짝수면 g-h 길을 가지 않았다는 뜻이다.

   이들을 제외한 목적지를 오름차순으로 출력하면 된다.

주의점

최단경로가 한가지가 아닐 수 있다는 점. 

g-h를 사용하는 최단경로가 있을 수 있고, 사용하지 않는 최단 경로 둘 다 있을 수 있다는 점. 

-> 짝수값과 홀수값으로 바꿈으로서 해결했지만 만약 다른 방법으로 풀 경우 꼭 고려

코드)

#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
 
#define INF 999999999
int T, n, m,t;
int s, g, h;
 
vector < vector<pair<int, int>>> load; //다음 도시, 도로 길이
vector <int> destination;
 
vector<int> Dijkstra(int start) {
    vector<int> dist(n + 1, INF);
    priority_queue <pair<int,int>> qu;
    qu.push({0,start});
    dist[start] = 0;
    while (!qu.empty())
    {
        int here = qu.top().second;
        int cost = -qu.top().first;
        qu.pop();
 
        if (dist[here] < cost) continue;
 
        for (int i = 0; i < load[here].size(); i++) {
            int next = load[here][i].first;
            int n_cost = cost + load[here][i].second;
            if (dist[next] > n_cost) {
                dist[next] = n_cost;
                qu.push({ -n_cost,next });
            }
        }    
    }
    return dist;
}
int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%d %d %d", &n, &m, &t);//교차료 도로 목적지 개수
        load.resize(n + 1);
        destination.resize(t);
        scanf("%d %d %d", &s, &g, &h);
        for (int i = 0; i < m; i++) {
            int a, b, d;//a b사이의 길이 d의 양방향도로
            scanf("%d %d %d", &a, &b, &d);
            if ((a == g && b == h) || (a == h && b == g)) {
                load[a].push_back({ b,d * 2 -1 });
                load[b].push_back({ a,d * 2 -1});
            }
            else {
                load[a].push_back({ b,d * 2 });
                load[b].push_back({ a,d * 2 });
            }
            
        }
        for (int i = 0; i < t; i++) {
            scanf("%d", &destination[i]);
        }
        //출발지에서 다익스트라 수행
        vector<int> dist = Dijkstra(s);
 
        //각 목적지에서 출발지까지의 경로 살핌, g랑 h를 지나서 왔는지
        vector <int> result;
        for (int i = 0; i < t; i++) {
            if (dist[destination[i]] == INF || (dist[destination[i]] % 2 == 0)) continue;
            result.push_back(destination[i]);
        }
        sort(result.begin(), result.end());
        for (int i = 0; i < result.size(); i++) {
            printf("%d ", result[i]);
        }
        printf("\n");
        load.clear();
        destination.clear();
    }
    return 0;
}