백준 10282번 해킹 (다익스트라,C++)

다익스트라 시간복잡도 : ElogV (연결된 정점 탐색 x 가장가까운 지점 정렬) 

다익스트라 주의점: 음의 가중치가 있을때 무한 사이클이 생길수 있음

#include<iostream>
#include<vector>
#include<queue>
#define INF 100000000

using namespace std; 

typedef pair<int, int> ci; 

vector<int> dijkstra(vector<vector<ci>>&graph, vector<int>&dist,int start) {

	priority_queue<ci, vector<ci>, greater<>>pq; 
	dist[start] = 0; 
	pq.push({ 0,start });

	while (!pq.empty()) {
		int w = pq.top().first;
		int e = pq.top().second;
		pq.pop(); 

		if (dist[e] < w)continue; 

		for (int i = 0; i < graph[e].size(); i++) {
			int ne = graph[e][i].first;
			int nw = graph[e][i].second; 
			if (dist[ne] > (w + nw)) {
				dist[ne] = (w + nw);
				pq.push({ dist[ne],ne });
			}
		}
	}
	return dist;

}

int main()
{
	int T;
	cin >> T;
	while (T--) {

		int n, d, c;
		cin >> n >> d >> c; 
		int a, b, s; //b->a s초
		vector<vector<ci>>graph; 
		graph.assign(n + 1, vector<ci>()); 
		vector<int>dist;
		dist.assign(n + 1,INF);

		for (int i = 0; i < d; i++) {
			cin >> a >> b >> s; 
			graph[b].push_back({ a,s });
		}

		dist=dijkstra(graph, dist,c); 

		//감염된 컴퓨터 수, 마지막 컴퓨터까지 걸리는 시간 
		int cnt = 0;
		int maxs = -1; 
		for (int i = 1; i <= n; i++) {
			if (dist[i] != INF) {
				cnt++;
				if (maxs < dist[i])maxs = dist[i];
			}
		}
		cout << cnt << ' ' << maxs << '\n';
	}

}