[백준][C++] 1753: 최단경로

문제 링크: https://www.acmicpc.net/problem/1753

 

문제 이름에서도 볼 수 있듯이 최단경로 문제입니다. 정말 기본형중의 기본형입니다.

벨만포드 알고리즘이나 다익스트라 알고리즘을 사용하면 됩니다.

공부할 겸 다익스트라 알고리즘 코드를 안보고 구현해봤는데 역시 실수가 있었습니다. 역시 갈길이 멉니다.

 

#pragma GCC optimize ("Ofast")
#define _CRT_SECURE_NO_WARNINGS
#define _SILENCE_CXX17_C_HEADER_DEPRECATION_WARNING

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



const int INF = 987654321;

vector<pair<int, int>> adj[20000];	// idx, cost

int main()
{
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
#endif

	ios_base::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);
	

	int v, e, k;
	cin >> v >> e >> k;
	--k;

	for (int i = 0; i < e; ++i) {
		int u, v, w;
		cin >> u >> v >> w;
		
		--u, --v;
		adj[u].emplace_back(v, w);
	}

	priority_queue<pair<int, int>> pq;	// cost(-), idx
	vector<int> dist(v, INF);
	dist[k] = 0;
	pq.emplace(0, k);

	while (!pq.empty()) {
		auto [cost, idx] = pq.top();
		pq.pop();

		cost = -cost;

		if (dist[idx] < cost) continue;

		for (auto& edge : adj[idx]) {
			auto next = edge.first;
			auto nextDist = cost + edge.second;

			if (dist[next] > nextDist) {
				dist[next] = nextDist;
				pq.emplace(-nextDist, next);
			}
		}
	}

	for (auto& d : dist) {
		if (d == INF)
			cout << "INF\n";
		else
			cout << d << '\n';
	}

	return 0;
}

다익스트라 알고리즘으로 푼 코드입니다