P2865 [USACO06NOV] Roadblocks G

思路：严格次短路，在任何情况下如果发现一条从1到i的路，都有以下情况：

        1.该路径小于当前1到i的最短路，将最短路替换

         2.该路径长度等于当前最短路，舍去

        3.该路径大于最短路且小于次短路，将此路径替换次短路，

        4.该路径长度大于或等于目前次短路，舍去

我们要跳出整个最短路，枚举所有边，这个时候可以我们可以预处理两条最短路，因为是双向边，我们用一个d[ ][0]数组表示1到其他点的最短路，d[ ][1]数组表示其他点到n的最短路

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=5e3+10,M=2e5+10;
struct node{
	int nxt,to,dis;
}e[M];
int n,m,x,y,z,h[N],ct;
void add(int x,int y,int z){
	e[++ct].nxt=h[x],e[ct].to=y,e[ct].dis=z,h[x]=ct;
}//链式前向星
int d[N][2];//两种不同状态
bool vis[N];
queue<int> q;
void spfa(int s){
	memset(d,0x7f,sizeof(d));
	q.push(s);
	vis[s]=1;
	d[s][0]=0;
	while(!q.empty()){
		int u=q.front();
		vis[u]=0;
		q.pop();
		for(int i=h[u];i;i=e[i].nxt){
			int v=e[i].to;
			if(d[v][0]>d[u][0]+e[i].dis){
				d[v][1]=d[v][0];
				d[v][0]=d[u][0]+e[i].dis;
				if(!vis[v])vis[v]=1,q.push(v);
			}
			if(d[v][1]>d[u][0]+e[i].dis&&d[u][0]+e[i].dis>d[v][0]){
				d[v][1]=d[u][0]+e[i].dis;
				if(!vis[v])vis[v]=1,q.push(v);
			}
			if(d[v][1]>d[u][1]+e[i].dis){
				d[v][1]=d[u][1]+e[i].dis;
				if(!vis[v])vis[v]=1,q.push(v);
			}
		}
	} 
}//spfa做次短路
int main(){
	ios::sync_with_stdio(0);
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>x>>y>>z;
		add(x,y,z);
		add(y,x,z);//双向建边
	}
	spfa(n);
	cout<<d[1][1]<<endl;
}