[백준 1916] 최소비용 구하기

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

풀이

일반적인 다익스트라구현은O(V^2)이고, 우선순위큐를 활용한 다익스트라구현은 O(ElogV)인데, 입력범위를 보면

v^2=1,000,000이고, 2^10은 1024이므로 대략 ElogV=1,000,000쯤이므로 어떠한 방법을 사용하던지 pass를 받을 수 있습니다.

저는 우선순위큐를 이용한방법으로 풀었습니다. 

주의할 것은, "a에서 b로 가는길이 있다는것은 b에서 a로 가는길이 있다" 를 의미하는게 아니므로, 이 문제는

무방향그래프가 아닌 방향그래프입니다. 그것말고는 딱히 주의할것은 없는 것 같습니다.

코드

#include<iostream>
#include<queue>
#include<vector>
using namespace std;
int INF = 100000000;
vector < pair<int, int>>a[1001];
int d[1001];
void dijkstra(int start);
int main()
{
	cin.tie(0);
	cin.sync_with_stdio(false);
	int n, m, v1, v2, w, start, end;
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		d[i] = INF;

	for (int i = 0; i < m; i++)
	{
		cin >> v1 >> v2 >> w;
		a[v1].push_back(make_pair(v2, w));
	}
	cin >> start >> end;
	dijkstra(start);
	
	cout << d[end] << '\n';
}
void dijkstra(int start)
{
	d[start] = 0;
	priority_queue<pair<int, int>>pq;
	pq.push({ 0, start });
	while (!pq.empty())
	{
		int current = pq.top().second;
		int distance = -pq.top().first;
		pq.pop();
		//최단거리가 아니면 skip
		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));
			}

		}
	}
	
}

결과