首页 > 代码库 > BZOJ1726: [Usaco2006 Nov]Roadblocks第二短路
BZOJ1726: [Usaco2006 Nov]Roadblocks第二短路
1726: [Usaco2006 Nov]Roadblocks第二短路
Time Limit: 5 Sec Memory Limit: 64 MBSubmit: 768 Solved: 369
[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)
HINT
Source
Gold
题解:
一个好思路就是 以1为起点和以n为起点各做一次SPFA,这样只要枚举每条边用 d[0][i]+d[1][e[j].go]+e[j].w更新答案即可
代码:
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cmath> 4 #include<cstring> 5 #include<algorithm> 6 #include<iostream> 7 #include<vector> 8 #include<map> 9 #include<set>10 #include<queue>11 #define inf 100000000012 #define maxn 5000+10013 #define maxm 100000+10014 #define ll long long15 using namespace std;16 inline ll read()17 {18 ll x=0,f=1;char ch=getchar();19 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}20 while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();}21 return x*f;22 }23 struct edge{int from,go,next,w;}e[2*maxm];24 int n,m,s,tot,q[maxn],d[2][maxn],head[maxn];25 bool v[maxn];26 void ins(int x,int y,int z)27 {28 e[++tot].go=y;e[tot].from=x;e[tot].w=z;e[tot].next=head[x];head[x]=tot;29 }30 void insert(int x,int y,int z)31 {32 ins(x,y,z);ins(y,x,z);33 }34 void spfa(int t)35 {36 for(int i=1;i<=n;++i) d[t][i]=inf;37 memset(v,0,sizeof(v));38 int l=0,r=1,x,y;39 s=(t==0)?1:n;q[1]=s;d[t][s]=0;40 while(l!=r)41 {42 x=q[++l];if(l==maxn)l=0;v[x]=0;43 for(int i=head[x];i;i=e[i].next)44 if(d[t][x]+e[i].w<d[t][y=e[i].go])45 {46 d[t][y]=d[t][x]+e[i].w;47 if(!v[y]){v[y]=1;q[++r]=y;if(r==maxn)r=0;}48 }49 }50 }51 int main()52 {53 freopen("input.txt","r",stdin);54 freopen("output.txt","w",stdout);55 n=read();m=read();56 while(m--)57 {58 int x=read(),y=read(),z=read();insert(x,y,z);59 } 60 spfa(0);spfa(1);61 int ans=inf;62 for(int i=1;i<=n;i++)63 {64 for(int j=head[i];j;j=e[j].next)65 {66 int tmp=d[0][i]+d[1][e[j].go]+e[j].w;67 if(tmp!=d[0][n])ans=min(ans,tmp);68 }69 }70 printf("%d\n",ans);71 return 0; 72 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。