- 看视频看了好久才理解的啊啊啊啊啊啊啊啊啊啊
- 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