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;
}
|
