BOJ 1753 - 최단경로

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

1753번: 최단경로

 

접근 방법

최단 경로를 구하는 알고리즘 중, 학부 수업에서 배운 다익스트라를 사용하기로 했다.

다익스트라에 대한 내용은 추후 따로 포스팅을 해야겠다.

 

간단하게 원리는 다음과 같다.

 

1. 모든 정점에 최단경로 d를 저장한다. (초기화는 무한으로)

2.  priority_queue에 최단 경로 d를 기준으로 오름차순이 되게 한다.

3. pq에서 뽑은 정점을 가지고, 간선으로 연결된 반대편 정점의 최단 경로 d를 최신화한다.

4. 3번 과정을 빌 때까지 진행한다.

 

이를 통해 쉽게 문제를 해결할 수 있다.

하지만, 수행시간이 1초라는 점이 핵심이다.

 

[ 고려해봐야 할 것]

    1. cin, cout 동기화 해제

    2. endl 대신 \n 사용하기

    3. { } 대신 make_pair 사용하기

 

필자의 경우 3번 때문에 많은 시도를 하였다...

이에 대한 정보를 찾기가 쉽지  않다.

 

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

#define MAX 20010
#define INF 987654321

using namespace std;

int v, e, s;
int dis[MAX];
vector<pair<int, int>> edge[MAX];


int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> v >> e >> s;
	
	for (int i = 0; i < e; i++) {
		int a, b, w;
		cin >> a >> b >> w;
		edge[a].push_back(make_pair(b,w));
	}
	
	// 최단 거리 초기화
	for (int i = 1; i <= v; i++) {
		dis[i] = INF;
	}

	// 시작 노드 세팅
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
	dis[s] = 0;
	pq.push(make_pair( 0, s ));

	while (!pq.empty()) {

		int topDis = pq.top().first;
		int topId = pq.top().second;
		pq.pop();
		if (dis[topId] < topDis)
			continue;

		// top에 연결된 간선을 이용해 최단거리 갱신
		for (int i = 0; i < edge[topId].size(); i++) {
			int oppo = edge[topId][i].first;
			int value = edge[topId][i].second;

			if (dis[oppo] > topDis + value) {
				dis[oppo] = topDis + value;
				pq.push(make_pair(topDis + value, oppo));
			}
			
		}
	}
	
	for (int i = 1; i <= v; i++) {
		if (dis[i] == INF)
			cout << "INF\n";
		else
			cout << dis[i] << '\n';
	}
}