[13911] 집 구하기

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

13911번: 집 구하기

시작 지점이 여러개인 다익스트라를 맥도날드/스타벅스에 대해 두번 돌려준다.

하나의 다익스트라가 끝나면, 거리를 맥세권/스세권인 경우에는 그대로 유지하고, 그렇지 않을때 INF로 바꿔둔다.

두번에 걸친 다익스트라가 끝나면, 각 다익스트라에서 구한 dst1[i]+dst2[i]의 최소를 찾으면 된다.

맥도날드나 스타벅스가 존재하는 정점은 dst1[i]+dst2[i]이 최소이더라도, 집이 없기에 답의 후보가 될 수 없으므로,

이를 처리하기 위한 bool[MAX_V]를 하나 더 두어 예외처리할 수 있겠다.

---

#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>;

const ll MAX_N = 10000, INF = (ll)1e16;

ll n, m, s, e, dst[MAX_N + 1], ansDist[MAX_N + 1][2];

typedef struct {

    ll idx, cost;

} state;

vector<state> adj[MAX_N + 1];

bool isEmptyNode[MAX_N + 1];

void dijkstra(int num) {

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

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

    fill(dst, dst + MAX_N + 1, INF);

    ll S, X;

    cin >> S >> X;

    while (S--) {

        ll s;

        cin >> s;

        isEmptyNode[s] = false;

        q.push({s, 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]});

            }

        }

    }

    for (ll i = 1; i <= n; i++) ansDist[i][num] = (dst[i] <= X) ? dst[i] : INF;

    return;

}

int main(void) {

    if (!local) {

        ios_base::sync_with_stdio(0);

        cin.tie(0);

    }

    memset(isEmptyNode, true, sizeof(isEmptyNode));

    cin >> n >> m;

    ll i;

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

        ll A, B, C;

        cin >> A >> B >> C;

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

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

    }

    dijkstra(0);

    dijkstra(1);

    ll ans = INF;

    for (i = 1; i <= n; i++) {

        if (!isEmptyNode[i]) continue;

        ans = min(ansDist[i][0] + ansDist[i][1], ans);

    }

    if (ans >= INF) ans = -1;

    cout << ans;

    return 0;

}

---