백준 1916번: 최소비용 구하기 - 다익스트라 C++

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

1916번: 최소비용 구하기

 

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


int res[1001];

struct Node {
	int x, dist;

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

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

	memset(res, 0x3f, sizeof(res));

	int n, m, st, end;
	vector<Node> map[1001];

	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int a, b, c;
		cin >> a >> b >> c;

		map[a].push_back({ b,c });
	}
	cin >> st >> end;

	priority_queue<Node> Q;

	Q.push({ st,0 });
	res[st] = 0;

	while (!Q.empty()) {
		int x = Q.top().x;
		int d = Q.top().dist;
		Q.pop();

		
		if (res[x] < d) continue;
		
		res[x] = d;
		if (x == end) {
			cout << d << '\n';
			return 0;
		}

		for (int i = 0; i < map[x].size(); i++) {
			int nx = map[x][i].x;
			int nd = map[x][i].dist;

			if (res[nx] > nd + d) {
				Q.push({ nx,nd + d });
			}

		}
	}

	return 0;
}

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

백준 1916