最短路

 1 #include<iostream>
 2 #include<vector>
 3 #include<queue>
 4 #include<cstdio>
 5 using namespace std;
 6 #define int long long
 7 const int inf = 0x3f3f3f3f3f3f3f3f;
 8 vector<pair<int, int>> vr[400010];
 9 int dis[200010], book[200010], pre[200010],now[200010];
10 void dijkstra(){
11     memset(dis, inf, sizeof(dis));
12     priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
13     dis[1] = 0;
14     q.push(make_pair(0, 1));
15     while (!q.empty()) {
16         int x = q.top().first;
17         int y = q.top().second;
18         q.pop();
19         if (book[y] == 1)continue;
20         book[y] = 1;
21         for (auto it : vr[y])
22             if (it.second + x < dis[it.first]) {
23                 dis[it.first] = it.second + x;
24                 pre[it.first] = y;
25                 q.push(make_pair(dis[it.first], it.first));
26             }
27                 
28     }
29 }
30 void solve(){
31     int n, m;
32     scanf("%lld %lld", &n, &m);
33     while (m--){
34         int u, v, w;
35         scanf("%lld %lld %lld", &u, &v, &w);
36         vr[u].push_back(make_pair(v, w));
37         vr[v].push_back(make_pair(u, w));
38     }
39     dijkstra();
40     if (dis[n] < inf) {
41         int noww = n, cnt = 0;
42         while (noww >= 1) {
43             now[cnt++] = noww;
44             noww = pre[noww];
45         }
46         for (int i = cnt - 1; i >= 0; i--)printf("%d ",now[i]);
47     }
48     else printf("-1");
49 }
50 signed main(){
51     int t = 1;
52     while (t--)
53         solve();
54     return 0;
55 }