双端队列代码

#include <bits/stdc++.h>
using namespace std;
struct node{
	int to,nxt,val;
}edge[20005];
int head[20005]={0},num=0,n,p,k;
void add(int u,int v,int w){
	edge[++num].to=v;
	edge[num].nxt=head[u];
	edge[num].val=w;
	head[u]=num;
	return;
} 
int cnt=0,frt,tmp,dis[1005]={0};
deque <int> q;
bool vis[1005]={0};
bool chk(int x){
	memset(dis,0x3f,sizeof(dis));
	q.push_back(1);
	memset(vis,0,sizeof(vis));
	vis[1]=1;dis[1]=0;
	while(!q.empty()){
		frt=q.front();
		q.pop_front();
		for(int i=head[frt];i;i=edge[i].nxt){
			tmp=edge[i].to;
			if(edge[i].val<=x){
				if(dis[tmp]>dis[frt]){
					dis[tmp]=dis[frt];
					if(!vis[tmp]){
						q.push_front(tmp);
						vis[tmp]=1;
					}
				}
			}
			else if(dis[tmp]>dis[frt]+1){
				dis[tmp]=dis[frt]+1;
				if(!vis[tmp]){
					vis[tmp]=1;
					q.push_back(tmp);
				}
			}
		}
	}
	if(dis[n]>k) return false;
	return true;
}
int main(){
	int u,v,w,l=0,r=0,mid;
	cin>>n>>p>>k;
	for(int i=1;i<=p;i++){
		scanf("%d%d%d",&u,&v,&w);
		add(u,v,w);
		add(v,u,w);
		r=max(r,w);
	}
	w=r;
	while(l<r){
		mid=(l+r)>>1;//k+1长电话线长度 
		if(chk(mid)) r=mid;//合法，尝试减小长度 
		else l=mid+1;
	}
	if(r==w&&!chk(w)) r=-1;
	cout<<r<<endl;
	return 0;
}

SPFA代码

#include <bits/stdc++.h>
using namespace std;
struct node{
	int to,nxt,val;
}edge[20005];
int head[20005]={0},num=0,n,p,k;
void add(int u,int v,int w){
	edge[++num].to=v;
	edge[num].nxt=head[u];
	edge[num].val=w;
	head[u]=num;
	return;
} 
int cnt=0,frt,tmp,dis[1005]={0};
queue <int> q;
bool vis[1005]={0};
bool chk(int x){
	memset(dis,0x3f,sizeof(dis));
	q.push(1);
	memset(vis,0,sizeof(vis));
	vis[1]=1;dis[1]=0;
	while(!q.empty()){
		frt=q.front();
		q.pop();
		for(int i=head[frt];i;i=edge[i].nxt){
			tmp=edge[i].to;
			if(edge[i].val<=x){
				if(dis[tmp]>dis[frt]){
					dis[tmp]=dis[frt];
					if(!vis[tmp]){
						q.push(tmp);
						vis[tmp]=1;
					}
				}
			}
			else if(dis[tmp]>dis[frt]+1){
				dis[tmp]=dis[frt]+1;
				if(!vis[tmp]){
					vis[tmp]=1;
					q.push(tmp);
				}
			}
		}
		vis[frt]=0;
	}
	if(dis[n]>k) return false;
	return true;
}
int main(){
	int u,v,w,l=0,r=0,mid;
	cin>>n>>p>>k;
	for(int i=1;i<=p;i++){
		scanf("%d%d%d",&u,&v,&w);
		add(u,v,w);
		add(v,u,w);
		r=max(r,w);
	}
	w=r;
	while(l<r){
		mid=(l+r)>>1;//k+1长电话线长度 
		if(chk(mid)) r=mid;//合法，尝试减小长度 
		else l=mid+1;
	}
	if(r==w&&!chk(w)) r=-1;
	cout<<r<<endl;
	return 0;
}