백준/1753번(최단 경로)/C++

문제 설명

 

Dijkstra 알고리즘을 활용해볼 수 있는 간단한 문제

 

주의할 점:

1. 가중치가 가장 작은 간선을 구할 때, 직접 비교하면 시간이 초과하므로 우선순위큐를 활용한다.

2. cin,cout은 scanf,printf보다 오래 걸린다.

 

 

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

#define MAX 20010
#define INF 987654321

using namespace std;

int V, E, start;
vector<pair<int, int>> a[MAX];
int d[MAX];

void dijkstra() {
	priority_queue<pair<int, int>> pq;
	d[start] = 0;
	pq.push(make_pair(0, start));

	while (pq.empty() == 0) {
		int current = pq.top().second;
		int cDistance = -pq.top().first;
		pq.pop();

		if (d[current] < cDistance) continue;

		for (int i = 0; i < a[current].size(); i++) {
			int next = a[current][i].first;
			int nDistance = a[current][i].second;
			if (nDistance + cDistance < d[next]) {
				d[next] = nDistance + cDistance;
				pq.push(make_pair(-d[next], next));
			}
		}
	}

	for (int i = 1; i <= V; i++) {
		if (d[i] == INF) cout << "INF" << "\n";
		else cout << d[i] << "\n";
	}
}


int main(void) {
	//cin,cout의 속도를 줄여주는 코드
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> V >> E >> start;

	for (int i = 1; i <= V; i++) {
		d[i] = INF;
	}

	for (int i = 0; i < E; i++) {
		int v1, v2, e;
		cin >> v1 >> v2 >> e;
		a[v1].push_back(make_pair(v2, e));
	}

	dijkstra();

	return 0;
}

 

 

디버깅 기록

: Dijkstra 알고리즘을 구현할 줄 안다면 그렇게 까다로운 문제가 아니지만,  우선순위큐가 우선순위를 계산할 때 pair의 first값을 먼저 비교하고 그 후에 second를 비교한다는 것을 간과하고 처음 코딩할 때 간선의 가중치값을 second에 넣어서 생각보다 오랜 시간을 허비했다;;  cin,cout은 scanf,print보다 느리지만 속도를 빠르게 해주는 코드를 활용하면 오히려 더 빠르다는 것을 깨달았다. 오름차순 우선순위큐를 생성할 때 greater를 사용하는 방법도 존재한다.