해킹(다익스트라 알고리즘)

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

10282번: 해킹

 

 

 그래프의 신장트리에서 최장거리를 구해야하는 내용이라 다익스트라라고 생각하기 어려웠다.

 

 다익스트라 알고리즘은 분명 두 버텍스 사이의 최단거리를 구하는 알고리즘이지만.

 알고리즘의 내용 자체는 특정 버텍스를 기준으로 연결된 모든 버텍스의 최단거리를 구하게 된다.

 즉, 다익스트라 알고리즘을 사용한 뒤, 각 버텍스까지의 거리를 저장한 리스트를 선형탐색하면 탐색한 버텍스의 수와 가장 먼 버텍스까지의 거리도 도출해낼 수 있다.

 

 다익스트라 알고리즘의 내용은 연결된 버텍스까지의 거리중 가장 짧은 거리를 갖고있는 연결을 선택하여 신장트리를 넓혀가므로, 가장 마지막에 탐색된 버텍스의 거리를 구해도 괜찮을 것 같다.

 

 1. 특정 버텍스를 기준으로 다익스트라 알고리즘을 사용.

 2. 각 버텍스까지의 거리를 저장한 리스트 생성, 리스트의 초기값은 INT_MAX(혹은 최대한 큰 수)

 3. 다익스트라 알고리즘이 끝난 후 2항의 리스트에서 INT_MAX가 아닌 값들의 수가 탐색된 버텍스의 수, INT_MAX가 아닌 수 중 가장 큰 수가 최장거리

 

#include<iostream>
#include<vector>
#include<queue>
using namespace std;

#define INT_MAX 10000001

int Distance[10001];

int main()
{
	int cmd;
	cin >> cmd;
	while (cmd--)
	{
		int n, d, c;
		cin >> n >> d >> c;
		fill_n(Distance, 10001, INT_MAX);

		// 다음 버텍스, 거리
		vector<pair<int, int>> Graph[10001];
		while (d--)
		{
			int n1, n2, n3;
			cin >> n1 >> n2 >> n3;
			Graph[n2].push_back(pair<int, int>(n1, n3));
		}

		// 거리, 버텍스
		priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
		Distance[c] = 0;
		pq.push(pair<int, int>(Distance[c], c));
		while (!pq.empty())
		{
			int curdist = pq.top().first;
			int curcom = pq.top().second;
			pq.pop();
			if (Distance[curcom] < curdist) continue;
			for (int i = 0; i < Graph[curcom].size(); i++)
			{
				int nextcom = Graph[curcom].at(i).first;
				int nextdist = Graph[curcom].at(i).second;
				if (Distance[nextcom] > curdist + nextdist)
				{
					Distance[nextcom] = curdist + nextdist;
					pq.push(pair<int, int>(Distance[nextcom], nextcom));
				}
			}
		}

		int count = 0;
		int ret = 0;
		for (int i = 0; i < 10001; i++)
		{
			if (Distance[i] != INT_MAX)
			{
				count++;
				if (ret < Distance[i]) ret = Distance[i];
			}
		}

		cout << count << " " << ret << '\n';
	}
}