[백준 10282] 해킹

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

10282번: 해킹

요구사항

1. 연결에 완료되는 시간 구하기

2. 연결된 컴퓨터 수 구하기

 

풀이

다익스트라로 풀이한다.

1. 첫 방문일때 cnt++

2. 제일 긴 시간 구하기

 

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <functional>
using namespace std;
struct go {
	int x;
	int z;
};
int n, d, s;
int dist[10010];
int visit[10010];
int main() {
	int t;
	scanf("%d", &t);
	for (int tc = 1; tc <= t; tc++) {
		vector<go> v[10010];
		int anscnt = 1;
		priority_queue < pair<int, int>, vector<pair<int, int>>, greater<pair<int,int>> > q;
		
		scanf("%d%d%d", &n, &d, &s);
		for (int i = 1; i <= n; i++) {
			dist[i] = 987654321;
			visit[i] = 0;
		}
		for (int i = 0; i < d; i++) {
			int x, y, z;
			scanf("%d%d%d", &x, &y, &z);
			v[y].push_back({ x,z });
		}
		q.push({ 0, s });
		dist[s] = 0;
		visit[s] = 1;

		while (!q.empty()) {
			//cout << "A" << endl;
			int nowdist = q.top().first;
			int nownode = q.top().second;
			q.pop();

			for (int i = 0; i < v[nownode].size(); i++) {
				int nextnode = v[nownode].at(i).x;
				int nextvalue = nowdist + v[nownode].at(i).z;
			//	cout << "N" << nextvalue << endl;
				if (dist[v[nownode].at(i).x] > nextvalue) {
					if (visit[v[nownode].at(i).x] ==0) anscnt++;
					visit[nextnode] = 1;
					//cout << "B" << endl;
					dist[v[nownode].at(i).x] = nextvalue;
					q.push({ nextvalue,nextnode });
				}

			}
		}
		int anstime = 0;
		for (int i = 1; i <= n; i++) {
			if (dist[i] >anstime && dist[i] != 987654321) {
				anstime = dist[i];
			}
		}
		printf("%d %d\n", anscnt, anstime);

	}
}