在OI Wiki上，对于dij算法的证明有说到 在所有边权值非负的前提下，Dijkstra 算法的正确性 而我在本题使用二分ans+最短路的时候，dij跑出的答案是错的，而只有SPFA跑的是对的，对此疑惑不解，求证明dij的不可用性（玄关）

二分+dij：

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+1e4,inf=1e9+7;
struct two{
	int d,u;
};
bool operator<(const two x,const two y){
	return x.d<y.d;
}
bool operator>(const two x,const two y){
	return x.d>y.d;
}
struct heap{
	two a[20*N];
	int n;
	two top(){
		return a[1];
	}
	void push(two x){
		a[++n]=x;
		int p=n;
		while (p!=1){
			if (a[p]<a[p/2]){
				swap(a[p],a[p/2]);
				p/=2;
			}
			else break;
		}
	}
	void pop(){
		a[1]=a[n];
		--n;
		int pp,p=1;
		while ((p<<1)<=n){
			pp=(p<<1);
			if (pp+1<=n&&a[pp+1]<a[pp]) ++pp;
			if (a[p]<a[pp]){
				swap(a[p],a[pp]);
				p=pp;
			}
			else break;
		}
	}
	bool empty(){
		return n==0;
	}
	void memsets(){
		n=0;
	}
}t;
struct rec{
	int e,nex,d;
}z[2*N];
int en,fi[N];
struct pai{
	int s,e,d;
}a[N];
bool cmp(const pai x,const pai y){
	return x.d<y.d;
}
void add(int s,int e,int d){
	++en;
	z[en].d=d;
	z[en].e=e;
	z[en].nex=fi[s];
	fi[s]=en; 
}
int n,p,k;
int dp[N];
bool vis[N];
bool dij(int d,int st,int ed){
	t.memsets();
	for (int i=1;i<=n;++i) fi[i]=0; 
	en=0;
	for (int i=1;i<=p;++i){
		if (a[i].d<=d){
			add(a[i].s,a[i].e,0);
			add(a[i].e,a[i].s,0);
		}
		else {
			add(a[i].s,a[i].e,1);
			add(a[i].e,a[i].s,1);
		}
	}
	for (int i=1;i<=n;++i){
		dp[i]=inf;vis[i]=false;
	}
	dp[st]=0;
	two x,y;
	x.u=st;x.d=0;
	t.push(x);
	while (t.empty()==false){
		x=t.top();
		t.pop();
		if (vis[x.u]==true) continue;
		vis[x.u]=true;
		for (int i=fi[x.u];i!=0;i=z[i].nex){
		//	printf("x.u=%d dp[z[i].e]=%d z[i].e=%d dp[x.u]=%d z[i].d=%d\n",x.u,dp[z[i].e],z[i].e,dp[x.u],z[i].d);
			if (dp[z[i].e]>dp[x.u]+z[i].d){
				dp[z[i].e]=dp[x.u]+z[i].d;
				y.u=z[i].e;y.d=dp[z[i].e];
				t.push(y);
			}
		}
	}
	return (dp[ed]<=k)?true:false;
}
int work(){
	int l=0,r=p+1,mid;
	while (l<r){
		mid=(l+r)>>1;
		if (dij(a[mid].d,1,n)==true) r=mid;
		else l=mid+1;
	}
	return l;
}
int ans;
int main(){
//	freopen("1.out","w",stdout);
	scanf("%d%d%d",&n,&p,&k);
	for (int i=1;i<=p;++i){
		scanf("%d%d%d",&a[i].s,&a[i].e,&a[i].d);
	}
	a[0].d=0;
	sort(a+1,a+1+p,cmp);
	ans=work();
	if (ans==p+1) printf("-1");
	else printf("%d",a[ans].d);
	return 0;
} 

二分+SPFA：

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+1e4,inf=1e9+7;
struct two{
	int d,u;
};
queue<two>t;
struct rec{
	int e,nex,d;
}z[2*N];
int en,fi[N];
struct pai{
	int s,e,d;
}a[N];
bool cmp(const pai x,const pai y){
	return x.d<y.d;
}
void add(int s,int e,int d){
	++en;
	z[en].d=d;
	z[en].e=e;
	z[en].nex=fi[s];
	fi[s]=en; 
}
int n,p,k;
int dp[N];
bool vis[N];
bool dij(int d,int st,int ed){
	for (int i=1;i<=n;++i) fi[i]=0; 
	en=0;
	for (int i=1;i<=p;++i){
		if (a[i].d<=d){
			add(a[i].s,a[i].e,0);
			add(a[i].e,a[i].s,0);
		}
		else {
			add(a[i].s,a[i].e,1);
			add(a[i].e,a[i].s,1);
		}
	}
	for (int i=1;i<=n;++i){
		dp[i]=inf;vis[i]=false;
	}
	dp[st]=0;
	two x,y;
	x.u=st;x.d=0;
	t.push(x);
	vis[st]=true;
	while (t.empty()==false){
		x=t.front();
		t.pop();
		vis[x.u]=false;
		for (int i=fi[x.u];i!=0;i=z[i].nex){
		//	printf("x.u=%d dp[z[i].e]=%d z[i].e=%d dp[x.u]=%d z[i].d=%d\n",x.u,dp[z[i].e],z[i].e,dp[x.u],z[i].d);
			if (dp[z[i].e]>dp[x.u]+z[i].d){
				dp[z[i].e]=dp[x.u]+z[i].d;
				if (vis[z[i].e]==true) continue;
				y.u=z[i].e;y.d=dp[z[i].e];
				vis[z[i].e]=true;
				t.push(y);
			}
		}
	}
	return (dp[ed]<=k)?true:false;
}
int work(){
	int l=0,r=p+1,mid;
	while (l<r){
		mid=(l+r)>>1;
		if (dij(a[mid].d,1,n)==true) r=mid;
		else l=mid+1;
	}
	return l;
}
int ans;
int main(){
//	freopen("1.out","w",stdout);
	scanf("%d%d%d",&n,&p,&k);
	for (int i=1;i<=p;++i){
		scanf("%d%d%d",&a[i].s,&a[i].e,&a[i].d);
	}
	a[0].d=0;
	sort(a+1,a+1+p,cmp);
	ans=work();
	if (ans==p+1) printf("-1");
	else printf("%d",a[ans].d);
	return 0;
}