题目链接：

思路：先给容量从大到小排序，然后二分，每次都一次spfa一下，判断当前的cost[n]的值。。。

1 #include
      
        2 #include
       
         3 #include
        
          4 typedef long long ll; 5 const int MAXN=10000+10; 6 const ll inf=1e60; 7 using namespace std; 8 struct Node{ 9     int v,w,t;10 };11 vector
         
          mp[MAXN];12 ll cost[MAXN];13 ll weight[MAXN*5];14 int n,m,time;15 int limit;16 17 18 int cmp(const ll a,const ll b){19     return a>b;20 }21 22 23 void SPFA(int u){24     for(int i=1;i<=n;i++)cost[i]=inf;25     cost[1]=0;26     queue
          
           Q;27     Q.push(u);28     while(!Q.empty()){29         int u=Q.front();30         Q.pop();31         for(int i=0;i
           
            =limit){37 cost[v]=cost[u]+t;38 Q.push(v);39 }40 }41 }42 }43 44 int main(){45 int _case;46 scanf("%d",&_case);47 while(_case--){48 scanf("%d%d%d",&n,&m,&time);49 for(int i=1;i<=n;i++)mp[i].clear();50 memset(weight,0,sizeof(weight));51 for(int i=1;i<=m;i++){52 int u,v,w,t;53 scanf("%d%d%d%d",&u,&v,&w,&t);54 Node p1,p2;55 p1.v=u,p2.v=v;56 p1.t=p2.t=t;57 p1.w=p2.w=w;58 weight[i]=w;//用来记录每条路的容量;59 mp[u].push_back(p2);60 mp[v].push_back(p1);61 }62 sort(weight+1,weight+m+1,cmp);63 //二分64 int low=1,high=m;65 while(low<=high){66 int mid=(low+high)/2;67 limit=weight[mid];//每次都选择一个限制68 SPFA(1);69 if(cost[n]==inf||cost[n]>time){70 low=mid+1;71 }else 72 high=mid-1;73 }74 printf("%d\n",weight[low]);75 }76 return 0;77 }