[Baekjoon] 백준 1753번: 최단경로 (c++)

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

1753번: 최단경로

1. proirty queue를 가중치를 작은 순(오름차순) 정렬하도록 선언

2. pq의 첫번째 요소인 현재 노드를 u로, 두 번째 요소인 현재 가중치를 w로 설정하고

3. 현재 노드 u에 대하여 첫번째 요소 V, 두번째 요소 W

4. w + W 가 현재 dist[V]보다 작으면, dist[V] = w+W로 갱신한다.

5. pq에  다시 V를 기준으로 현재노드, 가중치 w+W를 추가한다.

 

2~5번을 큐가 빌때까지 반복하고, dist배열을 출력한다.

 

 

 

priority queue 사용에 익숙하지않아서 한참 헤매던 문제다 ㅠㅠ

pq에 (현재 노드, 현재 가중치) 를 저장하는데

기본 제공되는 greater로 초기화하면 pair의 첫번째 요소로 적용되기 때문에, 가중치 기준으로 오름차순 정렬하기 위해서는 

struct compare {
	bool operator()(pair<int, int>a, pair<int, int> b) {
		return a.second > b.second;
	}
};

이 함수를 추가했어야 한다는걸 한참 뒤에 깨달았다.

그래서 계속 시간초과가 나오는데 뭐가 문젠지 몰랐다...

 

---

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
#define INF 987654321
#define MAX 20003

struct compare {
	bool operator()(pair<int, int>a, pair<int, int> b) {
		return a.second > b.second;
	}
};
vector <pair<int, int>> inp[MAX];
priority_queue<pair<int, int>, vector<pair<int, int>>, compare > pq;
int dist[MAX];

int main() {
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	
	int n, m, s;
	int a, b, weight;
	cin >> n >> m;
	cin >> s;
	for (int i = 0; i < m; i++) {
		cin >> a >> b >> weight;
		inp[a].push_back(make_pair(b, weight));
	}

	for (int i = 1; i <= n; i++) { dist[i] = INF; }
	dist[s] = 0;

	pq.push(make_pair(s, 0));

	while (!pq.empty()) {
		int u = pq.top().first;
		int w = pq.top().second;
		pq.pop();

		for (int i = 0; i < inp[u].size(); i++) {
			int V = inp[u][i].first;
			int W = inp[u][i].second;

			if (w + W < dist[V]) {
				dist[V] = w + W;
				pq.push(make_pair(V, w+W));
			}
		}
	}
	
	for (int i = 1; i <= n; i++) {
	
		if(dist[i] == INF) cout << "INF\n";
		else cout << dist[i] << "\n";
	}
	return 0;
}