[9370] 미확인 도착지

https://www.acmicpc.net/problem/9370

9370번: 미확인 도착지

풀이는 크게 2가지가 가능한데, 구간을 잘라서 다익스트라를 그대로 여러번 돌리는 방법이 있고

그래프를 적절히 조작하여 "[1445] 일요일 아침의 데이트"처럼 푸는 방법이 있다.

---

#include <bits/stdc++.h>

using namespace std;

#ifdef ONLINE_JUDGE

constexpr bool local = false;

#else

constexpr bool local = true;

#endif

using ll = long long;

using pi = pair<ll, ll>;

constexpr ll MAX_N = 2000, INF = (ll)1e17;

ll n, m, t, s, g, h, e, path[MAX_N + 1];

double dst[MAX_N + 1];

typedef struct {

    ll idx;

    double cost;

} state;

vector<state> adj[MAX_N + 1];

void dijkstra(ll s) {

    auto cmp = [&](state& A, state& B) -> bool { return A.cost > B.cost; };

    priority_queue<state, vector<state>, decltype(cmp)> q(cmp);

    q.push({s, 0});

    for (ll i = 0; i <= MAX_N; i++) dst[i] = (double)(10000000.0);

    dst[s] = 0;

    while (!q.empty()) {

        state cur = q.top();

        q.pop();

        if (cur.cost > dst[cur.idx]) continue;

        for (auto& nxt : adj[cur.idx]) {

            if (dst[nxt.idx] > dst[cur.idx] + nxt.cost) {

                dst[nxt.idx] = dst[cur.idx] + nxt.cost;

                q.push({nxt.idx, dst[nxt.idx]});

                path[nxt.idx] = cur.idx;

            }

        }

    }

    return;

}

void findPath(vector<ll>& ret) {

    ll cur = e;

    path[s] = -1;

    for (;; cur = path[cur]) {

        if (cur <= 0) break;

        ret.push_back(cur);

    }

    reverse(ret.begin(), ret.end());

    return;

}

void init(void) {

    ll i;

    for (i = 0; i <= MAX_N; i++) adj[i].clear();

}

int main(void) {

    if (!local) ios_base::sync_with_stdio(0), cin.tie(0);

    ll tc, i, j;

    cin >> tc;

    while (tc--) {

        init();

        cin >> n >> m >> t >> s >> g >> h;

        for (i = 0; i < m; i++) {

            ll A, B;

            double C;

            cin >> A >> B >> C;

            if (A == g && B == h || B == g && A == h) C -= (0.5);

            adj[A].push_back({B, C});

            adj[B].push_back({A, C});

        }

        dijkstra(s);

        vector<ll> p;

        findPath(p);

        vector<ll> ans;

        for (i = 0; i < t; i++) {

            ll tar;

            cin >> tar;

            if (dst[tar] - (int)dst[tar] > 0.3) ans.push_back(tar);

        }

        sort(ans.begin(), ans.end());

        for (auto& i : ans) cout << i << ' ';

        cout << '\n';

    }

    return 0;

}

---