首页 > 其他分享 >最短路

最短路

时间:2023-07-31 10:33:34浏览次数:26  
标签:lld int 短路 dis include noww first

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

相关文章

  • 最短路
    无向图Dijkstra(只能解决正权边,单源)它的逻辑可以理解为走当前最近可到达的且无法确定它是不是最短路的一个点,找它的最短路点击查看代码voidsolve(){intn,m,s;cin>>n>>m>>s;memset(dis,0x3f,sizeof(dis));for(inti=1;i<=m;i++){inta,b,c;......
  • 图的最短路
    图的最短路:最短路问题分类:1.单源最短路,也就是只有一个起点终点单源最短路又可以分成边权为正与边权为负两类2.多源最短路,其中有多个起点与终点。存图方式:1.以邻接矩阵存储(也就是二维数组:g[i][j]=k表示i到j有一条长度为k的边),这种方式主要适用于稠密图(边数接近点数的平方......
  • 最短路模板总结
    最短路单源最短路所有边权都是正数朴素版Dijkstra算法(适用于稠密图)堆优化版Dijkstra算法(适用于稀疏图)存在负权边Bellman_Ford算法,用于仅存在负权边,并且对边数有限制Spfa算法对Bellman_Ford算法进行优化(容易被卡死)多源汇最短路可能不止一个起点,有很多询问,求任意......
  • Dijkstra 算法——求解最短路径问题
    Dijkstra算法——求解最短路径问题  迪杰斯特拉算法(Dijkstra'salgorithm)是一种用于解决单源最短路径问题的贪心算法。它可以找到从一个起始顶点到其他所有顶点的最短路径,并且适用于边的权重非负的图。算法步骤如下:创建一个数组dist,用于保存起始顶点到其他顶点的最短距离......
  • 维特比算法最短路径python
    维特比算法及其在最短路径问题中的应用引言在计算机科学领域,维特比算法(Viterbialgorithm)是一种常用的动态规划算法,用于寻找最有可能的状态序列。维特比算法最初由安德鲁·维特比(AndrewViterbi)在1967年提出,用于解码卷积码信号。后来,维特比算法在自然语言处理、语音识别、机器翻......
  • 最短路
    最短路\(Floyd\)算法\(Dijkstra\)算法\(SPFA\)算法 这些算法都很熟悉,基本的就不多说了。T11993小K的农场 差分约束,跑一遍\(spfa\)判断有没有负环就可以了。structnode{ intv,w;};intn,m;vector<node>e[N];intdis[N];boolflag[N];intcnt[N];boo......
  • 最短路之dijkstra算法
    dijkstra比之上次介绍的的bellman-ford算法的用途上最大的区别就是dijkstra只可用于求无负权边图中的最短路,堆优化后的dij比bellman-ford的复杂度(mn)更小(mlogn)代码源关于dijkstra的解释简单来讲就是每次选出一个没被选过的离起点最近的点,松弛这个点所在的每个边,直到所有点都被......
  • 最短路之 Bellman-ford 算法
    bellman-ford算法的思想:若有向图有n个点,m条边。扫描所有边,对每条边进行一次松弛(即对a,b为端点,权重为w的边,dist[b]=min(dist[a],dist[a]+w))重复此流程(最多重复n次)直到没有更新操作发生例题1bellmanford板子给你一张n个顶点m条边的有向简单图,顶点编号从1到......
  • 优化基础3——最短路径算法和蚁群算法
    1.复习了一下迪杰斯特拉和弗洛伊德算法具体参考[最短路径问题]—Dijkstra算法最详解-知乎(zhihu.com)Floyd算法详解通俗易懂-知乎(zhihu.com)迪杰斯特拉解决不了负边权问题,假如确定了一个点2,将他加入了visited集合此时有一个点3到点2的边是负边权,实际权重更小了,但是......
  • 同余最短路的转圈法
    学习自Alex_Wei的博客。同余最短路模板题:[国家集训队]墨墨的等式。已知长为\(n\)的序列\(a\)。对于不定方程\(\sum\limits_{i=1}^na_ix_i=b\;(x_i\ge0)\),问有多少\(b\in[l,r]\)可以使得方程有解。\(n\le12\),\(a_i\le5\times10^5\),\(l,r\le10^{12}\)。本文默认取模......