백준 1916: 최소비용 구하기

#include <iostream>
#include <vector>
#include <utility> // pair
#include <queue> // pq
#define MAX 1001
#define INF 999999999
using namespace std;

vector< pair<int, int> > graph[MAX]; // graph[from] = <to, weight>, <to, weight>, ...
vector<int> dist(MAX, INF);

void update(int from, int old, priority_queue< pair<int, int> > * pq) {
	int edge = graph[from].size();
	int i;

	for (i = 0; i < edge; i++) {
		int to = graph[from][i].first;
		int weight = graph[from][i].second;
		int newDist = old + weight;

		if (newDist < dist[to]) {
			dist[to] = newDist;
			pq->push(make_pair(-newDist, to));
		}
	}
}

void dijkstra(int src) {
	priority_queue< pair<int, int> > pq; // (-weight, from)
	dist[src] = 0;

	pq.push({ 0, src });
	while (!pq.empty()) {
		int weight = -pq.top().first;
		int from = pq.top().second;
		pq.pop();

		if (dist[from] < weight) continue;
		else update(from, weight, &pq);
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int N, M, src, dst, from, to, weight, i;

	cin >> N;
	cin >> M;
	
	for (i = 0; i < M; i++) {
		cin >> from >> to >> weight;
		graph[from].push_back(make_pair(to, weight));
	}
	cin >> src >> dst;

	dijkstra(src);

	cout << dist[dst] << endl;
	return 0;
}