[백준] 1753번 - 다익스트라 최단경로

가중치가 존재하는 정점들의 최단경로를 구해야 한다.

나는 블로그에 기록한 적이 있는 다익스트라 알고리즘을 이용했다.

 

#include <string>
#include <vector>
#include <iostream>
#include <queue>
#include <map>
#include <list>
#include <algorithm>
#include <climits>
#include <cstring>
using namespace std;

void Dijikstra(int here);

int vertex, ganseon;
int start;
//비용, 도착정점
vector<pair<int,int>> adjacent[20001];

int main()
{
	cin >> vertex >> ganseon;
	cin >> start;

	for (int i = 0; i < ganseon; i++)
	{
		int u, v, w;
		cin >> u >> v >> w;	
		adjacent[u].push_back(make_pair(w, v));
	}

	for (int i = 1; i <= vertex; i++)
	{
		Dijikstra(i);
	}
}

void Dijikstra(int here)
{
	if (start == here)
	{
		cout << 0 << '\n';
		return;
	}

	list<pair<int, int>> discovered;
	int best[20001];
	int answer = -1;

	memset(best, 0x7f, 20001 * sizeof(int)); //0x7f:INT_MAX보다 4작음

	discovered.push_back(make_pair(0, start));
	best[start] = 0;

	while (discovered.empty() == false)
	{
		list<pair<int, int>>::iterator bestIt;
		int bestCost = INT_MAX;

		//인접한 정점중 가장 가까운 정점을 bestIt으로 선정
		for (auto it = discovered.begin(); it != discovered.end(); ++it)
		{
			if (it->first < bestCost)
			{
				bestCost = it->first;
				bestIt = it;
			}
		}
		int cost = bestIt->first;
		int tempHere = bestIt->second;
		discovered.erase(bestIt);

		if (best[tempHere] < cost)
			continue;
	
		for (int there = 0; there < adjacent[tempHere].size(); there++)
		{
			int nextVertex = adjacent[tempHere][there].second;
			// 연결되지 않았으면 스킵.
			if (adjacent[tempHere][there].first == 0)
				continue;

			// 더 좋은 경로를 과거에 찾았으면 스킵.
			int nextCost = best[tempHere] + adjacent[tempHere][there].first;
			if (nextCost >= best[nextVertex])
				continue;

			if (nextVertex == here)			
				answer = nextCost;						
			
			discovered.push_back(make_pair(nextCost, nextVertex));
			best[nextVertex] = nextCost;
		}	
	}//loop 끝

	if (answer == -1)
		cout << "INF" << '\n';
	else
		cout << answer << '\n';
}

 

테스트 케이스들은 통과되었지만 시간 초과가 발생했다. 이것을 해결하기 위해서 우선순위 큐를 사용해야 했다.

 

#include <string>
#include <vector>
#include <iostream>
#include <queue>
#include <map>
#include <list>
#include <algorithm>
#include <climits>
#include <cstring>
using namespace std;

void Dijikstra();

int vertex, ganseon;
int start;
//비용, 도착정점
vector<pair<int,int>> adjacent[20001];
priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > >pq;

int main()
{
	cin >> vertex >> ganseon;
	cin >> start;

	for (int i = 0; i < ganseon; i++)
	{
		int u, v, w;
		cin >> u >> v >> w;	
		adjacent[u].push_back(make_pair(w, v));
	}
	
	Dijikstra();
	
}

void Dijikstra()
{
	int best[20001];
	int answer = -1;

	for (int i = 1; i <= vertex; i++)
	{
		best[i] = INT_MAX;
	}

	pq.push(make_pair(0, start));	
	best[start] = 0;

	while (pq.empty() == false)
	{
		//자동으로 오름차순 정렬하기 때문에 top을 구하고 pop하기만 하면 됨
		int w = pq.top().first;
		int u = pq.top().second;
		pq.pop();


		for (int i = 0; i < adjacent[u].size(); i++)
		{
			int nextW = adjacent[u][i].first;
			int v = adjacent[u][i].second;

			if (best[u] + nextW < best[v])
			{
				best[v] = best[u] + nextW;
				pq.push(make_pair(best[v], v));				
			}
		}
	}

	for (int i = 1; i <= vertex; i++)
	{
		if (best[i] == INT_MAX)
			cout << "INF" << '\n';
		else
			cout << best[i] << '\n';

	}
}

 

pair<int,int> 형식의 데이터를 받는 우선순위큐는 pair의 첫번째 인자를 기준으로 정렬한다.  greater인자를 사용하므로

pair의 첫번째 인자를 기준으로 오름차순한다. 우선순위 큐를 사용해 코드가 많이 줄어들었고 다익스트라 함수를 정점마다

반복하는 것이 아닌 한번만 실행시켜 시간 초과나지 않게 한다.