题目描述

　　贝茜把家搬到了一个小农场，但她常常回到FJ的农场去拜访她的朋友。贝茜很喜欢路边的风景，不想那么快地结束她的旅途，于是她每次回农场，都会选择第二短的路径，而不象我们所习惯的那样，选择最短路。  　　贝茜所在的乡村有R(1<=R<=100,000)条双向道路，每条路都联结了所有的N(1<=N<=5000)个农场中的某两个。贝茜居住在农场1，她的朋友们居住在农场N（即贝茜每次旅行的目的地）。  　　贝茜选择的第二短的路径中，可以包含任何一条在最短路中出现的道路，并且一条路可以重复走多次。当然第二短路的长度必须严格大于最短路（可能有多条）的长度，但它的长度必须不大于所有除最短路外的路径的长度。 

输入格式

输入文件的第1行为两个整数，N和R，用空格隔开；第2..R+1行: 每行包含三个用空格隔开的整数A、B和D，表示存在一条长度为D(1 <= D <= 5000)的路连接农场A和农场B。

输出格式

输出文件仅有一行为一个整数表示从农场1到农场N的第二短路的长度。

样例输入

4 4 1 2 100 2 4 200 2 3 250 3 4 100

样例输出

450

样例说明

最短路：1 -> 2 -> 4 (长度为100+200=300) 第二短路：1 -> 2 -> 3 -> 4 (长度为100+250+100=450)

题目分析

严格第二短路，双向spfa求出最短路，依次枚举每条边，求出边两边最短路与边权和的最小值

源代码

#include<algorithm> #include<iostream> #include<iomanip> #include<cstring> #include<cstdlib> #include<vector> #include<cstdio> #include<cmath> #include<queue> using namespace std; inline const int Get_Int() { int num=0,bj=1; char x=getchar(); while(x<'0'||x>'9') { if(x=='-')bj=-1; x=getchar(); } while(x>='0'&&x<='9') { num=num*10+x-'0'; x=getchar(); } return num*bj; } const int maxn=20005; struct Edge { int from,to,dist; }; struct Spfa { int n,m; vector<Edge>edges; vector<int>G[maxn]; bool inque[maxn]; int dist[maxn],used[maxn],path[maxn]; void init(int n) { this->n=n; edges.clear(); for(int i=1; i<=n; i++)G[i].clear(); } void AddEdge(int from,int to,int dist) { edges.push_back((Edge) { from,to,dist }); m=edges.size(); G[from].push_back(m-1); } bool main(int s) { for(int i=1; i<=n; i++)dist[i]=0x7fffffff/2; memset(inque,0,sizeof(inque)); deque<int>Q; Q.push_back(s); dist[s]=0; path[s]=s; inque[s]=1; used[s]++; while(!Q.empty()) { int Now=Q.front(); Q.pop_front(); inque[Now]=0; for(int i=0; i<G[Now].size(); i++) { Edge& e=edges[G[Now][i]]; int Next=e.to; if(dist[Next]>dist[Now]+e.dist) { dist[Next]=dist[Now]+e.dist; path[Next]=Now; if(!inque[Next]) { used[Next]++; if(used[Next]==edges.size())return false; //负权回环 if(!Q.empty()&&dist[Next]<dist[Q.front()])Q.push_front(Next); //SLF优化 else Q.push_back(Next); inque[Next]=1; } } } } return true; } void Output(int x) { if(path[x]==x) { cout<<x<<" "; return; } Output(path[x]); cout<<x<<" "; } }; Spfa spfa1,spfa2; int n,m,ans=0x7fffffff/2; int main() { n=Get_Int(); m=Get_Int(); spfa1.init(n); spfa2.init(n); for(int i=1; i<=m; i++) { int x=Get_Int(),y=Get_Int(),v=Get_Int(); spfa1.AddEdge(x,y,v); spfa1.AddEdge(y,x,v); spfa2.AddEdge(x,y,v); spfa2.AddEdge(y,x,v); } spfa1.main(1); spfa2.main(n); for(int i=1; i<=n; i++) for(int j=0; j<spfa1.G[i].size(); j++) { Edge& e=spfa1.edges[spfa1.G[i][j]]; if(spfa1.dist[e.from]+spfa2.dist[e.to]+e.dist<=spfa1.dist[n])continue; ans=min(ans,spfa1.dist[e.from]+spfa2.dist[e.to]+e.dist); } printf("%d\n",ans); return 0; }