해킹

#include<iostream>
#include<vector>
#include<queue>
#include<utility>
#include<cstring>
 
using namespace std;
 
int tc,n, d, c;
vector<pair<int, long long> > map[10000];
long long visit[10000];
bool dist[10000];
vector<pair<int, int> > vv;
int v;
int INF = 100000000;
 
 
void dijkstra(int start) {
    visit[start] = 0;
    dist[start] = true;
    priority_queue<pair<int, long long> > pq;
    pq.push(make_pair(start, 0));
    while (!pq.empty()) {
        int current = pq.top().first;
        int distance = -pq.top().second;
        pq.pop();
        if (visit[current] < distance) continue;
        for(int i = 0; i< map[current].size(); i++){
            int next = map[current][i].first;
            int nextDistance = distance + map[current][i].second;
            if (nextDistance < visit[next]) {
                visit[next] = nextDistance;
                dist[next] = true;
                pq.push(make_pair(next, -nextDistance));
            }
        }
    }
 
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> tc;
    for (int t = 0; t < tc; t++) {
        cin >> n >> d >> c;
        for (int i = 0; i < n; i++) {
            visit[i] = INF;
        }
        for (int i = 0; i < d; i++) {
            int a, b, s;
            cin >> a >> b >> s;
            //map[a - 1].push_back({ b - 1,s });
            map[b - 1].push_back({ a - 1,s });
        }
 
        dijkstra(c-1);
        int maxx = 0;
        for (int i = 0; i < n; i++) {
            if (visit[i] != INF)
                v++;
            if (visit[i] > maxx && visit[i] != INF)
                maxx = visit[i];
        }
        
        cout << v <<' '<<maxx <<'\n';
        for(int i = 0; i< n; i++){
            dist[i] = false;
        }
        for(int i = 0; i< n; i++){
            visit[i] = 0;
        }
        for (int i = 0; i < n; i++) {
            map[i].clear();
        }
        v = 0;
    }
    return 0;
}

다익스트라 알고리즘이다.

처음써봤고, 나동빈님 강의를 보고 풀어본 문제중 하나다.

컴퓨터 해킹갯수를 세는게, INF가 아닐때와 d가 true일때 생각해본건데..

INF개수를 세는게 맞았다