10282 : 해킹

풀이

안녕하세요 다욱스트라입니다

코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

int n, m, s;
struct edg {
    int idx, dst;
    bool operator <(edg A)const {
        return dst > A.dst;
    }
};

int main() {
    cin.tie(0); ios_base::sync_with_stdio(0);

    int tc;
    for (cin >> tc; tc; tc--) {
        cin >> n >> m >> s;

        vector<vector<edg> > gph(n+1);
        vector<int> dst(n+1, 1e9);
        priority_queue<edg> pq;

        for (int i = 0, u, v, w; i < m; i++) {
            cin >> u >> v >> w;
            gph[v].push_back({ u,w });
        }

        pq.push({ s,dst[s]=0 });
        while (!pq.empty()) {
            edg now = pq.top();
            pq.pop();
            if (now.dst != dst[now.idx]) continue;
            for (edg nxt : gph[now.idx]) {
                if (dst[nxt.idx] > dst[now.idx] + nxt.dst) {
                    dst[nxt.idx] = dst[now.idx] + nxt.dst;
                    pq.push({ nxt.idx,dst[nxt.idx] });
                }
            }
        }

        int cnt = 0, val = 0;
        for (int i = 1; i <= n; i++) if (dst[i] != 1e9) {
            cnt++;
            val = max(val, dst[i]);
        }

        cout << cnt << " " << val << "\n";
    }

    return 0;
}

아무말

백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이

wookje.kwon's profile image

wookje.kwon

2018-09-01 19:31

Read more posts by this author