贝茜把家搬到了一个小农场,但她常常回到FJ的农场去拜访她的朋友。贝茜很喜欢路边的风景,不想那么快地结束她的旅途,于是她每次回农场,都会选择第二短的路径,而不象我们所习惯的那样,选择最短路。 贝茜所在的乡村有R(1<=R<=100,000)条双向道路,每条路都联结了所有的N(1<=N<=5000)个农场中的某两个。贝茜居住在农场1,她的朋友们居住在农场N(即贝茜每次旅行的目的地)。 贝茜选择的第二短的路径中,可以包含任何一条在最短路中出现的道路,并且,一条路可以重复走多次。当然咯,第二短路的长度必须严格大于最短路(可能有多条)的长度,但它的长度必须不大于所有除最短路外的路径的长度。
【bzoj1726】【Usaco2006 Nov】【Roadblocks第二短路】【spfa】
发布日期:2021-11-16 15:38:51
浏览次数:1
分类:技术文章
本文共 1548 字,大约阅读时间需要 5 分钟。
Description
Input
* 第1行: 两个整数,N和R,用空格隔开
* 第2..R+1行: 每行包含三个用空格隔开的整数A、B和D,表示存在一条长度为 D(1 <= D <= 5000)的路连接农场A和农场B
Output
* 第1行: 输出一个整数,即从农场1到农场N的第二短路的长度
Sample Input
4 4
1 2 100
2 4 200
2 3 250
3 4 100
1 2 100
2 4 200
2 3 250
3 4 100
Sample Output
450
输出说明:
最短路:1 -> 2 -> 4 (长度为100+200=300)
第二短路:1 -> 2 -> 3 -> 4 (长度为100+250+100=450)
输出说明:
最短路:1 -> 2 -> 4 (长度为100+200=300)
第二短路:1 -> 2 -> 3 -> 4 (长度为100+250+100=450)
题解:
就是求严格次短路。
spfa的时候像序列那样讨论一下即可。
代码:
#include#include #include #define N 5010#define M 100010using namespace std;int point[N],next[M<<1],cnt,x,y,v,n,m,q[N*20],f[N],dis[N][2];struct use{int st,en,v;}e[M<<1];void add(int x,int y,int v){ next[++cnt]=point[x];point[x]=cnt;e[cnt].en=y;e[cnt].v=v;}void spfa(){ int h(0),t(1); memset(dis,127/3,sizeof(dis)); q[t]=1;f[1]=1;dis[1][0]=0; while (h dis[u][0]+e[i].v){ dis[v][1]=dis[v][0]; dis[v][0]=dis[u][0]+e[i].v; ff=1; } if (dis[v][0]==dis[u][0]+e[i].v&&dis[v][1]>dis[u][1]+e[i].v){ dis[v][1]=dis[u][1]+e[i].v; ff=1; } if (dis[v][0] dis[u][0]+e[i].v){ dis[v][1]=dis[u][0]+e[i].v; ff=1; } if (ff&&!f[v]){ f[v]=1; q[++t]=v; } } }} int main(){ scanf("%d%d",&n,&m); for (int i=1;i<=m;i++){ scanf("%d%d%d",&x,&y,&v); add(x,y,v);add(y,x,v); } spfa(); cout< <
转载地址:https://blog.csdn.net/sunshinezff/article/details/51142804 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
逛到本站,mark一下
[***.202.152.39]2024年04月03日 07时51分14秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
关于Adams安装过程中问题的解决记录
2019-04-28
kinova-Mico安装与调试
2019-04-28
Elmo运动控制器 —— Maestro Software编程实践指南
2019-04-28
Elmo运动控制器 —— Maestro Software结构和接口
2019-04-28
Power PMAC运动控制器 —— 学习笔记2
2019-04-28
运动控制 —— 强大的状态机工具
2019-04-28
Platinum Maestro运动控制器 —— PVT模式笔记
2019-04-28
Platinum Maestro运动控制器 —— 运动程序笔记
2019-04-28
PID算法原理及参数调整原则
2019-04-28
Platinum Maestro运动控制器 ——速度位置等数据的获取
2019-04-28
Platinum Maestro运动控制器 ——Ssh登录控制器
2019-04-28
基础笔记2 —— 不损失精度的前提下浮点数拆分成整型的方法浅析
2019-04-28
数据类型在内存中的存储
2019-04-28
循环神经网络(LSTM)实现股票预测-深度学习100例 | 第10天
2019-04-28
Python3--爬取数据之911网站信息爬取
2019-04-28
Python--format()学习记录
2019-04-28
Python--切片学习记录
2019-04-28
Python--判断一个字符串是否包含某子串的几种方法
2019-04-28
pandas包
2019-04-28
Python爬虫之图片爬取
2019-04-28