6) 백준 1753 - 최단경로

1753번: 최단경로 (acmicpc.net)

1753번: 최단경로

---

다익스트라 알고리즘을 사용했다.

#include <bits/stdc++.h>

using namespace std;

int vertex[20001]; // 정점으로 부터의 길이
int dij[20001];
int INF = 999999;

int main(void) {
	fill_n(dij, 20001, 11);
	fill_n(vertex, 20001, 999999);
	
	vector<vector<pair<int, int>> > dij(20001);
	
	int V, E, K, u, v, w;
	
	cin >> V >> E;
	cin >> K;
	
	for(int i = 0; i < E; i++) {
		cin >> u >> v >> w;
		dij[u].push_back(make_pair(v, w));
	}
	
	vertex[K] = 0;
	priority_queue<pair<int, int> > q;
	q.push(make_pair(-vertex[K], K));
	
	while(!q.empty()) {
		int start_point_vxt = -q.top().first;
		int start_point = q.top().second;
		for(int i = 0; i < dij[start_point].size(); i++) {
			int target = dij[start_point][i].first;
			if(vertex[target] > dij[start_point][i].second + vertex[start_point]) {
				vertex[target] = dij[start_point][i].second + vertex[start_point];
				q.push(make_pair(-vertex[target], dij[start_point][i].first));
			}
		}
		q.pop();
	}
	
	for(int i = 1; i <= V; i++) {
		if(vertex[i] < INF) {
			cout << vertex[i] << "\n";
		}
		else {
			cout << "INF" << "\n";
		}
	}
	
	return 0;
}

초기화 할때 0이 아닌 다른 수로 초기화를 하고 싶으면 memset이 아닌 fill_n을 사용해야한다!!

fill_n([배열명], [숫자를 변경(0부터)할 배열의 index수], [변경할 숫자]);

vertex 배열

    - K(시작 vertex)를 기준으로 각 Vertex에게 가는 비용 정리 ( 못갈 경우 999999, 본인(K)은 0 )

 

dij 배열

    - 처음에는 문제의 최대인 [200001][200001]로 했더니 메모리 초과....

    - 2차 vector로 사용

    - dij의 1차는 시작 Vertex, 2차는 pair로서 첫번째는 도착 Vertex 두번째는 비용

 

target : 어떤 Vertex(start_point)에서 이동이 가능한 Vertex들

 

Queue를 사용하면 시간이 너무 오래 걸린다.

다익스트라를 사용할 때는 최단 거리를 먼저 사용하므로 priority_queue를 사용하자.

단, top의 경우 큰 숫자로 정렬이 되기 때문에 음수값으로 저장하자. (다익스트라는 적은 비용부터 계산)