백준1735 - 최단경로

https://www.acmicpc.net/problem/1753

1753번: 최단경로

우선 순위 큐를 이용하여 다익스트라를 구현하였다. 우선순위 큐에 first자리는 거리의 비용이 들어가고 second자리는 도착하는 곳이 들어간다. 간선의 갯수가 300000개이기 때문에 first자리를 비용이 들어가게 해야만 한다. 도착한 위치에서 짧은 거리를 갱신하도록 하였고 우선 순위 큐는 first의 값이 큰 순서, 그 다음 second 값이 큰 순서로 비교하기 때문에 -(마이너스)를 붙여서 작은 비용이 맨 위에 가도록 하였다.(음수는 절댓값을 기준하면 절댓값이 작은놈이 크다.) 이렇게 하면 가장 작은 비용이 맨 위로 올라가게 된다. 참고로 다익스트라 알고리즘은 나동빈님 블로그에서 공부를 하였다.

 

#include <iostream>
#include <vector>
#include <queue>
#define INF 1000000 //무한대 설정
using namespace std;

int n, m; //n은 마을의 갯수, m은 경우의 수
int startposition; //시작하는 점

vector<pair<int, int>>v[20001]; //각 도시간의 비용을 담을 백터
int d[20001]; //다익스트라 결과

void dijkstra(int start) {
	d[start] = 0; //시작하는 지점은 0
	priority_queue<pair<int, int>> pq; //우선순위 큐 사용
	pq.push(make_pair(0, start)); //비용을 first, 시작하는 지점을 second로 설정
	while (!pq.empty()) { //우선순위 큐가 빌 때까지 반복
		int current = pq.top().second; //현재 마을을 currrent 설정

		int distance = -pq.top().first; //현재 비용에 -를 붙인다.(반복문에서 거리는 -가 붙여서 나오고 시작하는 순간은 비용이 0이기 때문에)
		pq.pop(); //front값 pop

		if (d[current] < distance) { //현재 도달할 수 있는 비용보다 크면 반복문 맨 위로 이동
			continue;
		}
		for (int i = 0; i < v[current].size(); i++) { //도달가능한 모든 도시를 탐색
			int next = v[current][i].second; //도달 가능한 도시를 초기화
			int nextDistance = distance + v[current][i].first; //도달 가능한 도시에 사용되는 비용을 초기화
			if (nextDistance < d[next]) { //도달 가능한 도시에 비용이 현재 도달 가능한 비용보다 작으면
				d[next] = nextDistance; //비용 갱신
				pq.push(make_pair(-nextDistance, next)); //우선 순위 큐에 -를 붙인 채 push
			}
		}
	}

}

int main() {
	cin >> n >> m;
	cin >> startposition;

	//처음은 다익스트라 결과 값을 담을 공간에 INF로 초기화
	for (int i = 1; i <= n; i++) {
		d[i] = INF;
	}

	//a도시에서 b도시까지 c비용이 걸린다는 것을 넣는다.
	for (int i = 0; i < m; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		v[a].push_back(make_pair(c, b));
	}
	
	dijkstra(startposition); //다익스트라 수행

	for (int i = 1; i <= n; i++) {
		if (d[i] == INF) { //무한대면
			cout << "INF" << '\n'; //"INF"로 출력
		}
		else {
			cout << d[i] << '\n';
		}
	}
}