交了10多次，后来把二分的下界l从0改成-1就AC。。。。。无法理解啊。。。。。。。。。。。。
PS:想通了。。。本来脑残想成只有N为0的时候才能dij才能取到0，但是因为能免费去边所以。。。下界必须取-1才能让上界可以取到0。。。真是脑残了。。。。
#include<iostream> #include<cstdio> #include<algorithm> #include<queue> #include<utility> #include<vector> #include<cstring> #define INF 0x3fffffff #define pb push_back #define pn(x) cerr<<x<<endl using namespace std; typedef long long ll; typedef pair<int,int> node; int N,P,K; const int maxv=1005; struct edge{ int to,w; }; vector<edge> G[maxv]; vector<edge> G2[maxv]; int dis[maxv]; bool dij(int m){ for(int i=1;i<=N;i++) for(int j=0;j<G[i].size();j++){ if(G[i][j].w<=m) G2[i][j].w=0; else G2[i][j].w=1; } memset(dis,0x3f,sizeof dis); dis[1]=0; priority_queue<node,vector<node>,greater<node> > Q; Q.push((node){dis[1],1}); while(!Q.empty()){ node now=Q.top(); Q.pop(); int u=now.second; if(dis[u]<now.first) continue; for(int i=0;i<G2[u].size();i++){ int v=G2[u][i].to; if(dis[u]+G2[u][i].w<dis[v]){ dis[v]=dis[u]+G2[u][i].w; Q.push((node){dis[v],v}); } } } return dis[N]<=K; } int main(){ freopen("in.txt","r",stdin); cin>>N>>P>>K; int t1,t2,t3; for(int i=0;i<P;i++){ scanf("%d%d%d",&t1,&t2,&t3); G[t1].pb((edge){t2,t3}); G2[t1].pb((edge){t2,t3}); G[t2].pb((edge){t1,t3}); G2[t2].pb((edge){t1,t3}); } if(N==1){ cout<<0<<endl; return 0; } int l=-1,r=1000006; while(r-l>1){ int mid=(r+l)>>1; if(dij(mid)) r=mid; else l=mid; } if(!dij(r)) cout<<-1<<endl; else cout<<r<<endl; return 0; }