首页 > 代码库 > bzoj1726 [Usaco2006 Nov]Roadblocks第二短路
bzoj1726 [Usaco2006 Nov]Roadblocks第二短路
1726: [Usaco2006 Nov]Roadblocks第二短路
Time Limit: 5 Sec Memory Limit: 64 MBSubmit: 826 Solved: 394
[Submit][Status]
Description
贝茜把家搬到了一个小农场,但她常常回到FJ的农场去拜访她的朋友。贝茜很喜欢路边的风景,不想那么快地结束她的旅途,于是她每次回农场,都会选择第二短的路径,而不象我们所习惯的那样,选择最短路。 贝茜所在的乡村有R(1<=R<=100,000)条双向道路,每条路都联结了所有的N(1<=N<=5000)个农场中的某两个。贝茜居住在农场1,她的朋友们居住在农场N(即贝茜每次旅行的目的地)。 贝茜选择的第二短的路径中,可以包含任何一条在最短路中出现的道路,并且,一条路可以重复走多次。当然咯,第二短路的长度必须严格大于最短路(可能有多条)的长度,但它的长度必须不大于所有除最短路外的路径的长度。
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的时候顺便维护个次短的长度
也可以正反各一遍最短路,然后枚举每一条边的dis[1][l]+dis[r][n]+v更新次短路(我就是这么做的)
还可以像k短路一样倒着跑最短路然后正着A*
#include<cstdio>#include<iostream>#include<cstring>using namespace std;struct ed{int x,y,z;}b[300010];struct edge{int to,next,v;}e[300010];int head[10001];int dis1[10001];int dis2[10001];int q[1000010];bool mrk[10001];int n,m,cnt,mx,ans=2147483647;inline void ins(int u,int v,int w){ e[++cnt].to=v; e[cnt].next=head[u]; e[cnt].v=w; head[u]=cnt;}inline void insert(int u,int v,int w){ ins(u,v,w); ins(v,u,w);}inline void spfa(int S,int *dis){ memset(mrk,0,sizeof(mrk)); memset(q,0,sizeof(q)); dis[S]=0;q[1]=S;mrk[S]=1; int t=0,w=1; while (t<w) { int now=q[++t]; for (int i=head[now];i;i=e[i].next) if (dis[e[i].to]>dis[now]+e[i].v) { dis[e[i].to]=dis[now]+e[i].v; if (!mrk[e[i].to]) { mrk[e[i].to]=1; q[++w]=e[i].to; } } mrk[now]=0; }}int main(){ scanf("%d%d",&n,&m); for (int i=1;i<=m;i++) { scanf("%d%d%d",&b[i].x,&b[i].y,&b[i].z); insert(b[i].x,b[i].y,b[i].z); } memset(dis1,127/3,sizeof(dis1)); memset(dis2,127/3,sizeof(dis2)); spfa(1,dis1); spfa(n,dis2); mx=dis1[n]; for (int i=1;i<=m;i++) { int now=dis1[b[i].x]+dis2[b[i].y]+b[i].z; now=min(now,dis1[b[i].y]+dis2[b[i].x]+b[i].z); if (now!=mx&&now<ans)ans=now; } for (int i=1;i<=n;i++) for(int j=head[i];j;j=e[j].next) ans=min(ans,dis1[i]+dis2[i]+e[j].v*2); printf("%d\n",ans);}
bzoj1726 [Usaco2006 Nov]Roadblocks第二短路
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。