广东制冷设备网站建设费用,川畅咨询 做网站多少钱,帮忙建网站的人,阿里云网站域名绑定引入
在计算机科学的世界里#xff0c;算法就像是星空中的繁星#xff0c;各自闪烁着智慧的光芒。它们沉默而坚定#xff0c;像是一群不语的哲人#xff0c;默默地解答着世界的问题。
算法的步骤#xff0c;如同优美的诗行#xff0c;让复杂的问题在流转的字符中得以释…引入
在计算机科学的世界里算法就像是星空中的繁星各自闪烁着智慧的光芒。它们沉默而坚定像是一群不语的哲人默默地解答着世界的问题。
算法的步骤如同优美的诗行让复杂的问题在流转的字符中得以释放。它们如同山间清泉从一座山峰流淌到另一座山峰涤荡着问题的尘埃揭示出真实的面貌。
它们像是一把把钥匙打开了通往计算机科学的大门。我们用它们来解决问题用它们来创造奇迹。它们是我们智慧的结晶是我们对世界的理解和对未来的憧憬。
走进这个充满算法的世界感受那智慧的光芒和诗意的韵律。让我们一起探索未知的领域寻找那最美的风景和最珍贵的宝藏。
算法不仅是计算机科学的基础更是我们生活的诗意所在。它们让我们看到了未来的希望感受到了科技的魅力。所以让我们一起拥抱算法让它们为我们的生活增添色彩为我们的世界带来更多的可能性。
算法就像是计算机科学中的一道道美食佳肴它们各自拥有独特的味道和风味。有些算法如同细腻的法式甜点复杂而精致需要我们耐心地逐一品味有些算法则如同朴实的乡村面包简单而实用让人感到亲切和温暖。
基本介绍
而在这茫茫的算法大海中有一种算法闪烁着亮丽的光彩——最短路算法。 最短路算法是一种图论算法用于在加权图中找到两个节点之间的最短路径。这种算法在现实生活中有着广泛的应用例如 交通规划最短路算法可以用于城市交通规划帮助确定最短路线以减少交通拥堵和提高交通效率。物流配送在物流配送中最短路算法可以帮助确定最短路径以最小化运输成本和时间。网络设计在计算机网络中最短路算法可以帮助确定最佳路由以确保数据包能够以最快的速度传输。地理信息系统在地理信息系统中最短路算法可以用于确定两点之间的最短路径例如在地图上查找两点之间的最佳路线。 其中SPFA是打开图论大门的一个钥匙就让我们走进它吧。
思路
归根结底SPFA就是宽搜看看就懂了。
#include bits/stdc.h
using namespace std;
struct edge{int x, y, c, pre;} a[410000];int alen, last[11100];
void ins(int x, int y, int c)//ins函数的功能是建立一条从x出发到y且长度为c的边
{a[alen] edge{x, y, c, last[x]}; 全局增加一条有向边并赋值last[x] alen; //建立边与边的联系都是从x出发
}int n, m, d[11100]; //d[i]表示目前i和出发点的最短距离
bool v[11100]; //v[i]等于true表示点i在更新队列中等于false表示点i不在更新队列中
void spfa()
{memset(d, 63, sizeof(d));d[1] 0; //初始化d数组出发点为1出发点到自己的距离为0memset(v, 0, sizeof(v)); v[1] 1; //初始化v数组v[1]等于1表示出发点1进入队列dequeint Q; Q.push_back(1); //定义更新队列出发点进入更新队列while (!Q.empty()) //只要队列不为空就表示还有点等着更新别的点{int x Q.front(); //从队列中取出准备好更新别的点的点xfor (int k last[x]; k; k a[k].pre) //重点理解k首相等于和x相连的最后一条边的编号。那么倒数第二条和x相连的边的编号是多少呢在a[k].next可以找到{int y a[k].y;if (d[y] d[x] a[k].c) //尝试用x的最短距离更新y的最短距离{d[y] d[x] a[k].c; //如果点被更新了那么它马上有冲动想进更新队列要去更新它的亲朋好友与之直接相连的点if (v[y] 0) //如果点y不在队列则进入队列如果已经在队列了则不用再进入。{Q.push_back(y);v[y] 1;}}}Q.pop_front(); //此时x已经更新完它的亲朋好友完成使命退出队列Qv[x] 0; //标记x已经不再队列以后x有可能会再次进入队列}//队列没有点等着更新别的点了那么意味着所有点的d值都是最优的if (d[n] d[0]) printf(-1\n); //d[0]为初始的最大值d[n]等于d[0]表示点n没有被更新即点n无法到达。else printf(%d, d[n]);
}
int main()
{scanf(%d%d, n, m);alen 0;memset(last, 0, sizeof(last)); //注意构图之前一定要初始化不然后果很严重for (int i 1; i m; i){int x, y, c;scanf(%d%d%d, x, y, c); //题目给出的是无向边而我们的边目录是有向边ins(x, y, c);ins(y, x, c); //建立正向边、反向边}spfa();return 0;
}
详细注释都写在代码里面了好好看。
例题
不放了上洛谷自己查吧. 据说一个欠揍的行为需要一张图来安慰。
