点击打开链接
题目要求 首先要按时到达 其次尽可能走最短路线
通过二分 看能否在以当前长度的边为最短边的情况下按时到达 若不能则下调 否则上调
因为一条路径中最短边越长 对这条路径中边的要求也就越高 某些费时更少的边就被排除了 可能导致无法按时到达
反之 超过时限的可能也就越小
#include <stdio.h> #include <vector> #include <queue> #include <algorithm> #define N 99999999 using namespace std; struct node1 { int v; long long cap; int con; }; struct node2 { friend bool operator < (node2 n1,node2 n2) { return n1.s>n2.s; } int id; int s; }; vector <struct node1> edge[10001]; long long len[50001]; long long ans; int dis[10001],book[10001]; int n,m,time,limit; void binsearch(); int calculate(); int main() { struct node1 t; long long c; int cnt,i,j,a,b,d; scanf("%d",&cnt); while(cnt--) { scanf("%d%d%d",&n,&m,&time); for(i=1;i<=n;i++) { edge[i].clear(); } for(i=1;i<=m;i++) { scanf("%d%d%lld%d",&a,&b,&c,&d); t.v=b,t.cap=c,t.con=d; edge[a].push_back(t); t.v=a,t.cap=c,t.con=d; edge[b].push_back(t); len[i]=c; } sort(len+1,len+m+1); binsearch(); printf("%lld\n",ans); } return 0; } void binsearch() { int l,mid,r; l=1,r=m,ans=len[l]; while(l<=r) { mid=(l+r)/2; limit=len[mid]; if(calculate()) { ans=len[mid]; l=mid+1; } else { r=mid-1; } } return; } int calculate() { priority_queue <struct node2> que; struct node1 t; struct node2 cur,tem; int i,p; for(i=1;i<=n;i++) { dis[i]=N; book[i]=0; } dis[1]=0; tem.id=1; tem.s=0; que.push(tem); while(!que.empty()) { cur=que.top(); que.pop(); p=cur.id; if(book[p]==1) continue; book[p]=1; for(i=0;i<edge[p].size();i++) { t=edge[p][i]; if(t.cap>=limit&&book[t.v]==0&&dis[t.v]>dis[p]+t.con) { dis[t.v]=dis[p]+t.con; tem.id=t.v; tem.s=dis[t.v]; que.push(tem); } } } if(dis[n]<=time) return 1; else return 0; }
