- 看视频看了好久才理解的啊啊啊啊啊啊啊啊啊啊
- Dijkstra(单源路径，贪心原理，负权边别来沾边)
我只会写堆化版，朴素版太过复杂了（自我感觉）
这是cf中的dijkstra题目，1900的难度，当时卡了三天。。。。
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 }
- Floyd(可处理多源路径问题，并可接受负权边）
标签：lld,int,短路,dis,include,noww,first From： https://www.cnblogs.com/DLSQS-lkjh/p/17592341.html