[백준] 1753-최단경로

 

다익스트라 알고리즘을 이용해서 해결해야 하는 문제입니다.

왜? 그냥 que를 이용해서 구현하면 안되나 생각했습니다. 결과는 

인접하는 정점으로 이동할때는 최소경로값으로 먼저 이동하면서 큐에 들어가는 갯수를 최소화 시켜줘야 합니다.

하나의 정점에서 모든 정점으로 이동하는 최소경로값 (양수만) 이기 때문에 해당 다익스트라 기법을 구현하면 됩니다.  

 

https://gusdnr69.tistory.com/133

c++ 우선순위 큐 priority_queue 사용법

 

그리고 또 조심하셔야 할게 vector를 사용하지 않고 20000 X 20000 배열을 생성하면 메모리 초과입니다..

 

이 두 가지를 조심하며 작성해주시면 됩니다.  

 

구현하는 방법은 bfs와 흡사합니다.

정답코드입니다.

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

int v = 0, e = 0, k = 0;

vector <pair <int, int>> arr[20001];
vector <int> result;

void solution(){

	for (int i = 0; i < v + 1; i++)
		result.push_back(123456789);

	priority_queue <pair <int, int>> que; //우선순위큐
	que.push(make_pair(0, k)); //초기비용0 과 시작점 // min 우선순위큐를 사용하기 위해서 음수값을 넣어주는 행동

	
	while (!que.empty() ) {
		int cost = -que.top().first; // -를 다시 붙여준다. 
		int pos = que.top().second;
	
		que.pop();

		if (result[pos] < cost) continue;
		
		for (int i = 0; i < arr[pos].size(); i++) {
			int adjacency_pos = arr[pos][i].first;
			int adjacency_cost = arr[pos][i].second;

			if (adjacency_cost + cost < result[adjacency_pos]) {
				result[adjacency_pos] = adjacency_cost + cost;
				que.push(make_pair(-result[adjacency_pos], adjacency_pos));
			}

		}
		
		
	}
	
	

}

int main() {

	int u, vv, w;
	
	cin >> v >> e >> k;
	

	for (int i = 0; i < e; i++) {
		cin >> u >> vv >> w;
		arr[u].push_back(make_pair(vv, w));
	}

	solution();
	
	for (int i = 1; i < result.size(); i++) {
		if (i == k)
			cout << 0 << '\n';
		else if (result[i] == 123456789)
			cout << "INF" << '\n';
		else
			cout << result[i] << '\n';
	}
	


	return 0;
}