题目：http://poj.org/problem?id=3662
二分答案。然后边权>mid的边的边权2记为1，否则记为0。找一个边权2的最短路，看dis[n]是否<=K。
别忘了不能到达要输出-1。
#include<iostream> #include<cstdio> #include<cstring> #include<queue> #define ll long long using namespace std; const int N=1005,M=10005,INF=16843009; int n,m,head[N],xnt,dis[N],K; ll l,r,ans; bool vis[N]; struct Edge{ int next,to;ll w;bool c; Edge(int n=0,int t=0,ll w=0,bool c=0):next(n),to(t),w(w),c(c) {} }edge[M<<1]; void add(int x,int y,int z) { edge[++xnt]=Edge(head[x],y,z,0);head[x]=xnt; edge[++xnt]=Edge(head[y],x,z,0);head[y]=xnt; } bool dj() { memset(dis,1,sizeof dis); memset(vis,0,sizeof vis); priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q; dis[1]=0;q.push(make_pair(0,1)); while(q.size()) { int k=q.top().second;q.pop(); while(vis[k]&&q.size())k=q.top().second,q.pop(); if(vis[k])break;vis[k]=1; for(int i=head[k],v;i;i=edge[i].next) if(dis[k]+edge[i].c<dis[v=edge[i].to]) { dis[v]=dis[k]+edge[i].c;q.push(make_pair(dis[v],v)); } } return dis[n]<=K; } int main() { scanf("%d%d%d",&n,&m,&K);int x,y;ll z; for(int i=1;i<=m;i++) { scanf("%d%d%lld",&x,&y,&z); add(x,y,z);r=max(r,z); } while(l<=r) { ll mid=((l+r)>>1); for(int i=1;i<=xnt;i++) { if(edge[i].w>mid)edge[i].c=1; else edge[i].c=0; } if(dj())ans=mid,r=mid-1; else l=mid+1; } if(dis[n]==INF)ans=-1; printf("%lld",ans); return 0; }