[백준 1753] 최단경로

문제출처: https://www.acmicpc.net/problem/1753

일반적인 선형탐색 다익스트라구현은 O(N^2)라 입력범위 때문에 당연히 시간초과가 뜰거라서, O(NlogN)방식의 풀이를 사용해야합니다.

우선순위큐를 활용한 방법이 있기때문에 그 방법을 사용했습니다.

모르시는분들은 손수 구현하기 힘드니 아래의 링크나 다른 자료들을 참고하시는게 좋을것 같습니다.!

https://jow1025.tistory.com/109

다익스트라를 구현하고 입력조건만 맞추면되므로 설명은 생략합니다.!

코드

#include<iostream>
#include<queue>
#include<vector>
int INF = 100000000;
using namespace std;

vector<pair<int, int>>a[20001];
int d[20001];
void dijkstra(int start);
int main()
{
	cin.tie(0);
	cin.sync_with_stdio(false);
	int V, E, k, u, v, w;
	cin >> V >> E >> k;
	for (int i = 1; i <= V; i++)
		d[i] = INF;

	for (int i = 0; i < E; i++)
	{
		cin >> u >> v >> w;
		a[u].push_back(make_pair(v, w));
	}
	dijkstra(k);
	for (int i = 1; i <= V; i++)
	{
		if (d[i] == INF)
			cout << "INF" << '\n';
		else cout << d[i] << '\n';
	}

}
void dijkstra(int start)
{
	d[start] = 0;
	priority_queue<pair<int, int>>pq;
	pq.push(make_pair(0, start));
	while (!pq.empty())
	{
		int distance = -pq.top().first;
		int current = pq.top().second;
		pq.pop();
		if (d[current] < distance)
			continue;

		for (int i = 0; i < a[current].size(); i++)
		{
			int next = a[current][i].first;
			int next_distance = distance + a[current][i].second;
			if (d[next] > next_distance)
			{
				d[next] = next_distance;
				pq.push(make_pair(-next_distance, next));
			}
		}
	}
}

결과