-
Notifications
You must be signed in to change notification settings - Fork 0
/
Dijkstra.cpp
74 lines (61 loc) · 1.32 KB
/
Dijkstra.cpp
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
#include<bits/stdc++.h>
using namespace std;
struct node {
int v, w;
};
const int mx = 1e5+7;
vector<node> adj[mx];
int visit[mx];
int parent[mx];
int dis[mx];
class cmp {
public:
bool operator()( node& a, node& b) {
return a.w>b.w;
}
};
int dijkstra(int source,int n) {
memset( parent,-1, sizeof(parent));
fill( dis,dis+mx,INT_MAX);
priority_queue<node,vector<node>,cmp> q;
q.push( {source,0});
dis[source] = 0;
while (!q.empty()) {
node tmp = q.top(); q.pop();
int u = tmp.v;
int cost = tmp.w;
if (n==u) return true;
visit[u] = true;
for (auto i: adj[u]) {
int v = i.v, w = i.w;
if ( !visit[v] && dis[u]+w<dis[v]) {
dis[v] = dis[u] + w;
parent[v] = u;
q.push( {v, dis[v]});
}
}
}
return false;
}
int main() {
int n, m;
cin >> n >> m;
for (int i = 0; i<m; i++) {
int x, y, w;
cin >> x >> y >> w;
adj[x].push_back({y,w});
adj[y].push_back( {x,w});
}
dijkstra(1,n);
stack<int> ans;
ans.push(n);
while ( parent[n]!=-1 ) {
n = parent[n];
ans.push(n);
}
while (!ans.empty()) {
cout << ans.top() << " ";
ans.pop();
}
cout << endl;
}