萌新求教 P2865 [USACO06NOV]路障

#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
int n,m,s,a,b,c,dis[100000],dis2[100000],st[100000],cnt;
bool vis[100000];
queue <int> q;
struct edge{
	int go;
	int last;
	int val;
}e[1000000];
void add(int x,int y,int z){
	e[++cnt].go=y;
	e[cnt].val=z;
	e[cnt].last=st[x];
	st[x]=cnt;
}
void spfa(int origin){
	for(int i=1;i<=n;i++)
		dis[i]=dis2[i]=2147483647;
	dis[origin]=0;
	vis[origin]=true;
	q.push(origin);
	while(!q.empty()){	
		int f=q.front();
		vis[f]=false;
		q.pop();
		for(int i=st[f];i!=0;i=e[i].last){
			int v=e[i].go;
			if(dis[v]>dis[f]+e[i].val){
				dis2[v]=dis[v];
				dis[v]=dis[f]+e[i].val;
				if(!vis[v]){
					vis[v]=true;
					q.push(v);
				}
			}
			else
			if(dis[v]<dis[f]+e[i].val&&dis2[v]>dis[f]+e[i].val){
				dis2[v]=dis[f]+e[i].val;
				if(!vis[v]){
					vis[v]=true;
					q.push(v);
				}
			}
			if(dis2[v]>dis2[f]+e[i].val){
				dis2[v]=dis2[f]+e[i].val;
				if(!vis[v]){
					vis[v]=true;
					q.push(v);
				}
			}
		}
		printf("%d\n",f);
		for(int i=1;i<=n;i++)
			printf("%d ",dis[i]);
		printf("\n"); 
		for(int i=1;i<=n;i++)
			printf("%d ",dis2[i]);
		printf("\n");
	}
}
int main(){
	scanf("%d %d",&n,&m);
	for(int i=1;i<=m;i++){
		scanf("%d %d %d",&a,&b,&c);
		add(a,b,c);
		add(b,a,c);
	}
	spfa(1);
	printf("%d ",dis2[n]);
	return 0;
}