백준 1753번 : 최단 경로 - 다익스트라 C++ 코드

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

1753번: 최단경로

 

#include <bits/stdc++.h>
using namespace std;

int ans[20001], v, e, st;

struct Node {
	int n, d;

	bool operator<(const Node& b) const {
		return d > b.d;
	}
};

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

	fill(ans, ans + 20001, -1);

	cin >> v >> e;
	cin >> st;

	vector<pair<int, int> > m[20001];

	for (int i = 0; i < e; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		m[a].push_back({ b,c });
	}

	priority_queue<Node> Q;
	Q.push({ st,0 });

	while (!Q.empty()) {
		int cur_node = Q.top().n;
		int cur_dist = Q.top().d;
		Q.pop();

		if (ans[cur_node] == -1) {
			ans[cur_node] = cur_dist;

			for (int i = 0; i < m[cur_node].size(); i++) {
				int nx = m[cur_node][i].first;
				if (ans[nx] == -1) {
					int nd = m[cur_node][i].second + cur_dist;
					Q.push({ nx,nd });
				}
			}
		}
	}


	for (int i = 1; i <= v; i++) {
		if (ans[i] == -1) cout << "INF\n";
		else cout << ans[i] << '\n';
	}


	return 0;
}

우선순위큐 최소힙을 이용해

다익스트라 알고리즘으로 풀 수 있다.

1753번 최단경로 메모리 및 시간