BZOJ1726: [Usaco2006 Nov]Roadblocks第二短路

1726: [Usaco2006 Nov]Roadblocks第二短路

Time Limit: 5 Sec Memory Limit: 64 MB
Submit: 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

Sample Output

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 1000000000
12 #define maxn 5000+100
13 #define maxm 100000+100
14 #define ll long long
15 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
",ans);
71     return 0;   
72 }

View Code