BOJ 9370 미확인 도착지

사용한 알고리즘

다익스트라, DFS

알고리즘 설명

이 문제는 그래프가 주어지고, 시작점 s가 주어진다.
g<->h사이를 지나갈때 도착지가 될 수 있는 곳 찾기.
먼저, s(시작점)으로 부터 다익스트라를 적용한다.
이후 도착점에서 최단 경로가 될 수 있는 Vertex를 찾아 들어간다.
들어가는 과정에서, 불가능 조건 2가지는 아래와 같다.
첫번째로, g<->h를 지나가지 않고 도착점으로 가는 경우.
두번째로, 시작점에서 연결되어 있지 않은 경우.
위 두가지를 제외하고, dfs의 시작과 다음 dfs 경로가 g와 h라면 정답이다.
이 정답을 정렬하여 출력한다.

풀이

// bakejoon 9370 yechan
#include <cstdio>
#include <algorithm>
#include <queue>
#include <utility>
#include <functional>
#include <vector>
using namespace std;
const int MAX_INF = 1e9;
typedef pair<int, int> P;

int T, n, m, t, s, g, h, a, b, d;
vector<vector<P>> adj;
vector<int> result;
vector<bool> visited;
vector<int> dist;

void Dijkstra(int start) {
    dist[start] = 0;
    priority_queue<P, vector<P>, greater<P> > PQ;
    PQ.push(P(0, start));

    while (!PQ.empty()) {
        int curr;
        do {
            curr = PQ.top().second;
            PQ.pop();
        } while (!PQ.empty() && visited[curr]);
        if (visited[curr]) break;
        visited[curr]=true;
        for (auto &p: adj[curr]) {
            int next=p.first, d=p.second;
            if (dist[next] > dist[curr] + d) {
                dist[next] = dist[curr] + d;
                PQ.push(P(dist[next], next));
            }
        }
    }
}

bool tracking(int curr) {
    if (dist[curr] == 0) return false;
    if (dist[curr] == MAX_INF) return false;
    bool ret=false;
    for (auto &p: adj[curr]) {
        int next=p.first, d=p.second;
        if (dist[next] == dist[curr]-d) {
            if (curr == g && next == h) return true;
            if (curr == h && next == g) return true;
            ret |= tracking(next);
        }
    }
    return ret;
}


int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d%d", &n, &m, &t);
        scanf("%d%d%d", &s, &g, &h);

        result.clear();
        adj = vector<vector<P> >(n+1);
        visited = vector<bool>(n+1, false);
        dist = vector<int>(n+1, MAX_INF);
        for (int i=0; i<m; i++) {
            scanf("%d%d%d", &a, &b, &d);
            adj[a].push_back(P(b,d));
            adj[b].push_back(P(a,d));
        }
        Dijkstra(s);

        for (int i=0; i<t; i++) {
            int x; scanf("%d", &x);
            if (tracking(x))
                result.push_back(x);
        }
        sort(result.begin(), result.end());
        for (int i=0; i<result.size(); i++)
            printf("%d ", result[i]);
        puts("");
    }
    return 0;
}