[BOJ] 백준 10282번 해킹 (C++ 코드)

🧨 백준 10282번 - 해킹

문제 난이도 : 골드4

문제 링크 : www.acmicpc.net/problem/10282

10282번: 해킹

🧨 알고리즘 선택 및 C++ 코드

#include <iostream>
#include <set>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

struct edge { int to, length; };
int cnt = 0;

int dijkstra(const vector<vector<edge>>& graph, int source, int target) {
    vector<int> min_distance(graph.size(), INT_MAX);
    min_distance[source] = 0;
    set<pair<int, int>> active_vertices;
    active_vertices.insert(make_pair(0, source));
    cnt = 0;
    int where = 0;
    while (!active_vertices.empty()) {
        where = active_vertices.begin()->second;
        cnt++;
        active_vertices.erase(active_vertices.begin());
        for (auto ed : graph[where]) {
            if (min_distance[ed.to] > min_distance[where] + ed.length) {
                active_vertices.erase(make_pair(min_distance[ed.to], ed.to));
                min_distance[ed.to] = min_distance[where] + ed.length;
                active_vertices.insert(make_pair(min_distance[ed.to], ed.to));
            }
        }
    }
    return min_distance[where];
}

int main() {
    int test;
    cin >> test;
    for (int t = 0; t < test; t++) {
        int n, d, c;
        cin >> n >> d >> c;
        vector<vector<edge>> graph(10001);
        for (int i = 0; i < d; i++) {
            int a, b, s;
            cin >> a >> b >> s;
            graph[b].push_back({ a, s });  // 유향그래프
        }
        int result = dijkstra(graph, c, n);
        cout << cnt << " " << result << "\n";
    }
}