10282번

10282번 - 해킹

양의 가중치를 갖는 그래프에서 최단거리를 구하는 것과 똑같은 문제이다.

따라서 다익스트라 알고리즘을 사용하여 문제를 풀 수 있다.

<정답 코드>

#include<iostream>
#include<vector>
#include<queue>
 
using namespace std;
const int INF = 987654321;
int main()
{
    int tc;
    scanf("%d", &tc);
    while (tc--)
    {
        int n, d, c;
        scanf("%d %d %d", &n, &d, &c);
        vector<vector<pair<int,int>>> v(n+1);
        vector<int> dist(n + 1,INF);
        for (int i = 0; i < d; i++)
        {
            int x,y,z;
            scanf("%d %d %d", &x, &y, &z);
            v[y].push_back({ x,z });
        }
 
        priority_queue<pair<int, int>> q;
        dist[c] = 0;
        q.push({ c,dist[c] });
 
        while (!q.empty())
        {
            int now = q.top().first;
            int cost = q.top().second;
            q.pop();
 
            if (cost > dist[now]) { continue; };
 
            for (int i = 0; i < v[now].size(); i++)
            {
                int next = v[now][i].first;
                int w = v[now][i].second;
                if (dist[next] > cost + w)
                {
                    dist[next] = cost + w;
                    q.push({ next,dist[next] });
                }
            }
            
        }
        int cnt = 0;
        int ans = 0;
        for (int i = 1; i <= n; i++)
        {
            if (dist[i] < INF)
            {
                cnt++;
                ans = ans < dist[i] ? dist[i] : ans;
            }
 
        }
 
        printf("%d %d\n", cnt, ans);
 
    }
 
    return 0;
}