BZOJ 1726 [Usaco2006 Nov]Roadblocks第二短路

题目大意

求第二短路= =

求第二短路的策略：

1. 如果边权都>0，跑两次Dijkstra()（一次从S，一次从T），之后枚举每一条边（如果是无向边需要枚举2次），如果S到该边一点距离+该边另一点到T距离+边长>最短路那么就尝试更新次短路。
2. 如果有边权< 0，Dijkstra() -> SPFA().
3. 如果有负权环，再见。

#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m,inx,iny,inz,dis[2][5010],use[5010],ans=0x3f3f3f3f;
int from[200010],to[200010],nex[200010],val[200010],head[5010],tot;
priority_queue<pair<int,int> >q;
void addedge(int tx,int ty,int tz) {from[++tot]=tx,to[tot]=ty,nex[tot]=head[tx],head[tx]=tot,val[tot]=tz;}
void dijkstra(int pos)
{
	memset(use,false,sizeof use);
	int id=(pos==n);
	dis[id][pos]=0;
	q.push(make_pair(0,pos));
	while(!q.empty())
	{
		int tmp=q.top().second;
		q.pop();
		if(use[tmp]) continue;
		use[tmp]=true;
		for(int i=head[tmp];i;i=nex[i])
			if(dis[id][to[i]]>dis[id][tmp]+val[i])
			{
				dis[id][to[i]]=dis[id][tmp]+val[i];
				if(!use[to[i]])q.push(make_pair(-dis[id][to[i]],to[i]));
			}
	}
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;++i) scanf("%d%d%d",&inx,&iny,&inz),addedge(inx,iny,inz),addedge(iny,inx,inz);
	memset(dis,0x3f,sizeof dis);
	dijkstra(1),dijkstra(n);
	for(int i=1;i<=tot;++i)
		if(dis[0][from[i]]+dis[1][to[i]]+val[i]!=dis[0][n]) ans=min(ans,dis[0][from[i]]+dis[1][to[i]]+val[i]);
	printf("%d\n",ans);
	return 0;
}