백준 1753번 C++

백준 1753번 최단경로

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

1753번: 최단경로

정답 코드

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

using namespace std;

int V, E;
int K;
int u, v, w;
int INF = 1000000;

vector<pair<int, int> > adj[20001];
int dist[20001];


void dijkstra(int src) {

	dist[src] = 0;
	priority_queue<pair<int, int> > pq;
	pq.push(make_pair(0, src));

	while (!pq.empty()) {
		int cost = -pq.top().first;
		int here = pq.top().second;
		pq.pop();

		if (dist[here] < cost) continue;

		for (int i = 0; i < adj[here].size(); i++) {
			int there = adj[here][i].first;
			int nextDist = cost + adj[here][i].second;

			if (dist[there] > nextDist) {
				dist[there] = nextDist;
				pq.push(make_pair(-nextDist, there));
			}
		}
	}
}

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

	cin >> V >> E;
	cin >> K;

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

	for (int i = 0; i < E; i++) {
		cin >> u >> v >> w;
		adj[u].push_back(make_pair(v, w));
	}

	dijkstra(K);

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

문제 풀이

다익스트라 알고리즘을 이용해서 풀 수 있는 문제입니다. 다익스트라 알고리즘은 최단경로를 구할 때 주로 이용하는 알고리즘입니다. 다익스트라 알고리즘은 여기를 누르시면 더 자세히 볼 수 있습니다. 다익스트라 알고리즘도 정석적인 풀이가 있으니 한 번 공부하시고 나서 풀어보시면 좋을 것 같습니다.