[10282] 해킹

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

10282번: 해킹

B->A로 가는 간선을 이어준뒤, 해킹된 컴퓨터를 시작으로 다익스트라를 돌린다

dst[]에서 INF가 아닌 원소의 개수가 곧 찾아야 하는 첫번째 답이고, dst[i]<INF인 dst[i]의 최대값이 두번째 답이된다.

---

#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)1e17;

ll n, m, s, dst[MAX_N + 1], path[MAX_N + 1];

typedef struct {

    ll idx, 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});

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

    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;

}

int main(void) {

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

    ll t;

    cin >> t;

    while (t--) {

        ll i, j;

        cin >> n >> m >> s;

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

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

            ll A, B, C;

            cin >> A >> B >> C;

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

        }

        dijkstra(s);

        ll ans = 0, cnt = 0;

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

            if (dst[i] >= INF) continue;

            cnt++;

            ans = max(dst[i], ans);

        }

        cout << cnt << ' ' << ans << '\n';

    }

    return 0;

}

---