http://poj.org/problem?id=3255

Bessie has moved to a small farm and sometimes enjoys returning to visit one of her best friends. She does not want to get to her old home too quickly, because she likes the scenery along the way. She has decided to take the second-shortest rather than the shortest path. She knows there must be some second-shortest path.

The countryside consists of R (1 ≤ R ≤ 100,000) bidirectional roads, each linking two of the N (1 ≤ N ≤ 5000) intersections, conveniently numbered 1..N. Bessie starts at intersection 1, and her friend (the destination) is at intersection N.

The second-shortest path may share roads with any of the shortest paths, and it may backtrack i.e., use the same road or intersection more than once. The second-shortest path is the shortest path whose length is longer than the shortest path(s) (i.e., if two or more shortest paths exist, the second-shortest path is the one whose length is longer than those but no longer than any other path).

Input

Line 1: Two space-separated integers: N and R
Lines 2.. R+1: Each line contains three space-separated integers: A, B, and D that describe a road that connects intersections A and B and has length D (1 ≤ D ≤ 5000)

Output

Line 1: The length of the second shortest path between node 1 and node N

Sample Input

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

Sample Output

450

Hint

Two routes: 1 -> 2 -> 4 (length 100+200=300) and 1 -> 2 -> 3 -> 4 (length 100+250+100=450)

 

 

次短路。

用Dijkstra，把最短路模板改几个地方。

在d[]最短路数组基础上，加一个次短路d2[]数组，全部初始化INF。

删去vis[]数组，结点u出堆后是否扩展取决于是否满足u.d>d2[u]，若满足，则次短路已找到，不扩展。

松弛操作分三类，大于d，小于d大于d2，小于d2。

堆里的d值既有最短路d，又有次短路d2。

为什么这样做是正确的呢？

在图G=(V,E)上，按照Dijkstra，在任意时刻将结点集分为黑色（已找到最短路），灰色（已发现），白色（未发现）三类。

在灰色结点集中任意一个结点出堆两次（后来直接continue掉的不计），第一次出堆必定找到了最短路，第二次出堆必定找到了次短路。（当然，如果不存在次短路，那么就没有第二次出堆）。这个的正确性与Dijkstra求最短路是一致的，都是利用三角不等式来进行贪心。因为当前这个u结点出堆，说明u.d是堆里所有结点d值最小的，不可能有别的路径到u的距离优于现有值。

配两张图来理解：

 

 

还有另一种做法：求出1到每一点的最短路，再求出每一点到n的最短路，枚举所有的边，1到n的经过该边的最短路径就有了，第二长的权和就是次短路长度。

#include<iostream>
#include<cstdio>
#include<queue>
#include<vector>
using namespace std;

struct Edge{
	int from,to,dist;
};
struct HeapNode{
	int u,d;
	bool operator < (const HeapNode& x)const{
		return d>x.d;
	}
};
int n,m;
vector<Edge> edges;
vector<int> G[5000+10];
int d[5000+10],d2[5000+10];

void init()
{
	edges.clear();
	for(int i=0;i<=n;i++)G[i].clear();
}

void AddEdge(int f,int t,int d)
{
	edges.push_back((Edge){f,t,d});
	G[f].push_back(edges.size()-1);
}

void dijkstra(int s)
{
	priority_queue<HeapNode> Q;
	for(int i=0;i<=n;i++)d[i]=(1<<30),d2[i]=(1<<30);
	d[s]=0;
	Q.push((HeapNode){s,0});
	while(!Q.empty())
	{
		HeapNode x=Q.top();
		Q.pop();
		int u=x.u;
		if(x.d>d2[u])continue;
		for(int i=0;i<G[u].size();i++)
		{
			Edge& e=edges[G[u][i]];
			int v=e.to;
			if(d[v]>x.d+e.dist)
			{
				d2[v]=d[v];
				d[v]=x.d+e.dist;
				Q.push((HeapNode){v,d[v]});
			}
			else if(x.d+e.dist>d[v]&&x.d+e.dist<d2[v])
			{
				d2[v]=x.d+e.dist;
				Q.push((HeapNode){v,d2[v]});
			}
		}
	}
}

int main()
{
//	freopen("input.in","r",stdin);
	cin>>n>>m;
	//init();
	int a,b,c;
	while(m--)
	{
		cin>>a>>b>>c;
		AddEdge(a,b,c);
		AddEdge(b,a,c);
	}
	dijkstra(1);
	cout<<d2[n]<<endl;
	return 0;
}