[C++] 백준 1916번 - 최소비용 구하기

Naive한 다익스트라 문제

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
#define INF 987654321
#define pii pair<int, int>

priority_queue<pii, vector<pii>, greater<pii>> pq;
int graph[1005][1005];
int dist[1005];
int n, m;
int u, v, w;
int start, last;

int main() {

	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> n >> m;

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			graph[i][j] = INF;
		}
	}

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

	for (int i = 0; i < m; i++) {
		cin >> u >> v >> w;
		if (graph[u][v] > w) graph[u][v] = w;
	}

	cin >> start >> last;

	dist[start] = 0;

	pq.push({ 0, start });

	while (!pq.empty()) {
		int x = pq.top().first;
		int U = pq.top().second;
		pq.pop();

		for (int i = 1; i <= n; i++) {
			int V = i;
			int W = graph[U][i];

			if (W == INF) continue;

			if (x + W < dist[V]) {
				dist[V] = x + W;
				pq.push({ x + W, V });
			}
		}
	}

	cout << dist[last] << endl;

	return 0;

}