[백준] 10282번 해킹

[적용한 알고리즘]

다익스트라

 

[아이디어]

내용

 

[생각의 흐름 / 절차] 

내용

 

[교훈]

잠이 안와서 푸는 기본문제2

 

<코드>

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

const int MAX_V = 20001;
const int INF = 1000000000;
typedef pair<int, int> P;

int main(){
    int t; scanf("%d", &t);

    while (t--){
        int V, E, K;
        vector<P> adj[MAX_V];
        scanf("%d %d %d", &V, &E, &K);

        for (int i = 0; i < E; i++){
            int from, to, cost;
            scanf("%d %d %d", &to, &from, &cost);
            adj[from].push_back(P(to, cost));
        }

        int dist[MAX_V];
        fill(dist, dist + MAX_V, INF);
        bool visited[MAX_V] = { 0 };
        priority_queue<P, vector<P>, greater<P>> PQ;

        dist[K] = 0;
        PQ.push(P(0, K));

        while (!PQ.empty()){
            int cur;
            do {
                cur = PQ.top().second;
                PQ.pop();
            } while (!PQ.empty() && visited[cur]);

            if (visited[cur]) break;

            visited[cur] = true;
            for (auto &p : adj[cur]){
                int nxt_node = p.first;
                int nxt_cost = p.second;

                if (dist[nxt_node] > dist[cur] + nxt_cost){
                    dist[nxt_node] = dist[cur] + nxt_cost;
                    PQ.push(P(dist[nxt_node], nxt_node));
                }
            }
        }
        int ans_cnt = 0;
        int ans_time = -1;

        for (int i = 1; i <= V; i++){
            if (dist[i] == INF) continue;
            ans_cnt++;
            ans_time = max(ans_time, dist[i]);
        }

        printf("%d %d\n", ans_cnt, ans_time);
    }
    return 0;
}