C++14(g++5.4) 解法, 执行用时: 18ms, 内存消耗: 920K, 提交时间: 2020-05-01 18:38:00

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
const int N=1100;
int n,p,k;
vector<P> v[N];
bool vis[N];
int d[N];
deque<int>de;
int bfs(int c) {
	memset(vis,0,sizeof(vis));
	memset(d,0x3f,sizeof(d));
	d[1]=0;
	de.push_back(1);
	int x,y,e;
	while(!de.empty()) {
		x=de.front();
		vis[x]=true;
		de.pop_front();
		for(int j=0; j<v[x].size(); j++) {
			y=v[x][j].first,e=v[x][j].second;
			if(vis[y])continue;
			if(e>c) {
				if(d[x]+1>=d[y])continue;
				d[y]=d[x]+1;
				de.push_back(y);
			} else {
				if(d[y]<=d[x])continue;
				d[y]=d[x];
				de.push_front(y);	
			}
		}
	}
	return d[n];
}
int main() {
	cin>>n>>p>>k;
	int a,b,c,maxc=0;
	for(int i=0; i<p; i++) {
		cin>>a>>b>>c;
		v[a].push_back(make_pair(b,c));
		v[b].push_back(make_pair(a,c));
		maxc=max(c,maxc);
	}
	if(bfs(maxc)>k) {
		cout<<-1<<endl;
		return 0;
	}
	int l=0,r=maxc;
	while(l<r) {
		int mid=(l+r)>>1;
		if(bfs(mid)<=k)r=mid;
		else l=mid+1;
	}
	cout<<l<<endl;
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 13ms, 内存消耗: 888K, 提交时间: 2020-09-12 22:37:45

#include<bits/stdc++.h>
using namespace std;

struct node1
{
	int x,y,w;
}E[10005];
struct node2
{
	int x,h;
}Q[10005];
vector<int>R[1005],W[1005];
int n,m,k;
bool judge(int s)
{
	int i,j,x,h,r=1,f=0,D[1005];
	for(i=1;i<=n;i++)W[i].clear(),D[i]=1e9;
	for(i=0;i<m;i++)
	{
		if(E[i].w>s)W[E[i].x].push_back(1),W[E[i].y].push_back(1);
		else W[E[i].x].push_back(0),W[E[i].y].push_back(0);
	}
	Q[0].x=1,Q[0].h=D[1]=0;
	while(r!=f)
	{
		x=Q[f].x,h=Q[f++].h;
		for(i=0;i<R[x].size();i++)
		{
			j=R[x][i];
			if(D[j]>h+W[x][i])Q[r].h=D[j]=h+W[x][i],Q[r++].x=j;
		}
	}
	return D[n]<=k;
} 
int main()
{
	int i,l,r,mid,ans=-1;
	scanf("%d%d%d",&n,&m,&k);
	for(i=0;i<m;i++)
	{
		scanf("%d%d%d",&E[i].x,&E[i].y,&E[i].w);
		R[E[i].x].push_back(E[i].y),R[E[i].y].push_back(E[i].x);
	}
	for(l=0,r=1e6;l<=r;)
	{
		mid=(l+r)>>1;
		if(judge(mid))ans=mid,r=mid-1;
		else l=mid+1;
	}
	printf("%d\n",ans);
    return 0;
}