P43859

p.cc

#include <iostream>
#include <vector>
#include <queue>
#include <utility>
#include <map>
using namespace std;


const int infinit = 999999999;


using Arc = pair<int, int>;			    // cost, destí
using Graph = vector<vector<Arc>>;      // llistes d'adjacència


int dijkstra(const Graph& G, int x, int y) {
	int n = G.size();
	vector<int> d(n, infinit);
	d[x] = 0;

	priority_queue<Arc, vector<Arc>, greater<Arc>> pq;
	pq.push({0, x});

	while (not pq.empty()) {
		int l = pq.top().first;
		int u = pq.top().second;
		pq.pop();

		if (d[u] >= l) {
			for (Arc a : G[u]) {
				int c = a.first;
				int v = a.second;
				if (d[v] > d[u] + c) {
					d[v] = d[u] + c;
					pq.push({d[v], v});
	}	}	}	}

	return d[y];
}


int main() {
	int n, m;
	while (cin >> n >> m) {
		Graph G(n);
		for (int i = 0; i < m; ++i) {
			int u, v, c;
			cin >> u >> v >> c;
			G[u].push_back({c, v});
		}
		int x, y;
		cin >> x >> y;

		int d = dijkstra(G, x, y);
		if (d == infinit) cout << "no path from " << x << " to " << y << endl;
		else cout << d << endl;
	}
}