summaryrefslogtreecommitdiff
path: root/cpp/dijkstra.cc
blob: 8aa63296d4e3617ff8c416f2e090270dcac5eb99 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <iostream>
#include <utility>
#include <list>
#include <vector>
#include <queue>
#include <fstream>
using namespace std;
#define INF 999999

typedef pair<int, int> pii;

list<pii> adj[INF];
int V; 
vector<int> previous(INF, -1);
int dijkstra(int src, int dest) {
	priority_queue<pii, vector<pii>, greater<pii> > pq;
	
	vector<int> dist(INF, INF);
	previous.resize(V);
	pq.push(make_pair(0, src));
	dist[src] = 0;
	while(!pq.empty()) {
		int u = pq.top().second;
		pq.pop();

		for(auto const& i : adj[u]) {
			int v = i.first;
			int w = i.second;

			if(dist[v] > dist[u] + w) {
				dist[v] = dist[u] + w;
				pq.push({dist[v], v});
				previous[v] = u;
			}
		}
	}

	return dist[dest];
}

void dijShortPath(int v, list<int>& path) {
/* example:
v = 6;
v = previous[6] (5)
v = previous[5] (2)
...
*/
	for(; v != -1; v = previous[v])
		path.push_front(v);
}

int main() {
/*
numVertici numArchi
sorgente destinazione
vertice1 vertice2 peso
...
*/
	cin >> V;
	int e, sorg, dest;
	cin >> e >> sorg >> dest;
	int u, v, w;
	for(int i = 0; i < e; i++) {
		cin >> u >> v >> w;
		adj[u].push_back(make_pair(v, w));
	}
	cout << dijkstra(sorg, dest) << endl;
	list<int> path;
	dijShortPath(dest, path);
	for(auto const& i : path)
		cout << i << ' ';

	return 0;
}