Baekjoon 10282번 해킹

문제

https://www.acmicpc.net/problem/10282

걸린 시간

00 : 48 : 25

풀이

C++

#include <bits/stdc++.h>
#define INF 1e9
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

void dijkstra(int src, vector<int>& dist, vector<pair<int, int>> adj[10001]){
    priority_queue<pair<int, int>> pq;
    pq.push(make_pair(src, 0));
    dist[src] = 0;
    while(!pq.empty()){
        int here = pq.top().first;
        int cost = -pq.top().second;
        pq.pop();
        if(dist[here] < cost) continue;
        for(int i = 0; i < adj[here].size(); i++){
            int there = adj[here][i].first;
            int nextDist = cost + adj[here][i].second;
            if(nextDist < dist[there]){
                dist[there] = nextDist;
                pq.push(make_pair(there, -nextDist));
            }
        }
    }
    int infect = 0, time = 0;
    for(int dest = 1; dest < dist.size(); dest++){
        if(dist[dest] != INF){
            infect++;
            time = max(time, dist[dest]);
        }
    }
    cout << infect << " " << time << "\n";
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int tc;
    cin >> tc;
    while(tc--){
        int n, d, c;
        cin >> n >> d >> c;
        vector<int> dist(n+1, INF);
        vector<pair<int, int>> adj[10001];
        for(int i = 0; i < d; i++){
            int a, b, s;
            cin >> a >> b >> s;
            adj[b].push_back(make_pair(a, s));
        }
        dijkstra(c, dist, adj);
    }
    return 0;
}

다익스트라를 잘 구현했지만 틀렸습니다를 받은 이유는 두가지가 있었다.

2차원 벡터에서 행에 해당하는 벡터의 개수만 초기화 하여 사용해 이전에 있던 값이 다음 테스트 케이스에 영향을 주었다.