[C++] 백준 10282 해킹 다익스트라알고리즘

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;

#define INF 987654321
const int maxCom = 10001;


int n, d, c, test;

void dijkstra(int start, int end, vector<pair<int, int>> *com);

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);  cout.tie(NULL);

	cin >> test;

	for (int i = 0; i < test; i++)
	{
		cin >> n >> d >> c;

		vector<pair<int, int>> computer[maxCom];

		for (int j = 0; j < d; j++)	//의존되고 있는 것을 기준으로 push_back한다.
		{
			int com, depen, hack;
			cin >> com >> depen >> hack;

			computer[depen].push_back({ com, hack });
		}

		dijkstra(c, n, computer);
	}

	return 0;
}

void dijkstra(int start, int end, vector<pair<int, int>> *com)
{
	int result = 0;	//감염된 컴퓨터개수
	int minDist = 0;	//최종 가장 적은 초
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
	vector<int> dist(n + 1, INF);	//초
	pq.push({ 0, start });
	dist[start] = 0;

	while (!pq.empty())
	{
		int currNode = pq.top().second;
		int currDist = pq.top().first;
		pq.pop();

		for (int i = 0; i < com[currNode].size(); i++)
		{
			int nextNode = com[currNode][i].first;
			int nextDist = com[currNode][i].second + currDist;

			if (dist[nextNode] > nextDist)	//현재노드와 다음갈 노드의 초의 합이 그곳에 도착한 것보다 작나
			{
				dist[nextNode] = nextDist;
				pq.push({ nextDist, nextNode });
			}
		}
	}

	for (int i = 1; i <= n; i++)	//계산 된 것을 토대로 감염된 개수와 가장 적은 초를 구한다.
	{
		if (dist[i] != INF)
		{
			result++;

			if (dist[i] > minDist)	//계산된 것중에 가장 큰 저장된 값이 최종값임
				minDist = dist[i];
		}
	}

	cout << result << " " << minDist << "\n";
}

 

해설, 풀이

1. 가장 적은 비용을 찾는 문제이다.
2. 감염시작된 컴퓨터에서부터 끝까지의 걸린 시간의 최소를 구한다.
3. 우선순위 큐를 사용하여 더 적은 비용의 합을 먼저 계산한다.
4. 풀이와 개수를 구하는 것을 따로한다.

priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

우선순위 큐를 사용할 때의 헷갈림을 조심한다.

 

다익스트라를 알고 풀게되면 이해하기 쉽다.

 

chanheess.tistory.com/80

다익스트라 알고리즘