hdu 1839 二分搜索+dijkstra最短路

小灰灰 2022-07-28 00:23 155阅读 0赞

[点击打开链接][Link 1]

题意: 给定一个无向图, 顶点从1-n, 给定m条边, 每条边有两个值, 一是这条边的最大容量, 二是经过这条边需要的时间, 要求从1顶点开始,到n顶点结束,在满足总时间不超过T的情况下, 所能运的最大的容量是多少(最大的容量应该是经过的路径中最小的路径的容量).

分析: 到最后的容量一定是在图中最小的边的容量和最大的边的容量之间, 并且满足单调性(如果到终点最大的容量是C, 比C小的容量也能运到终点), 有了单调性, 就可以用二分查找了, 二分容量的限制, 在满足容量限制的情况下看看能否在T时间之内到达n这个点.

#include<bitset>
    #include<map>
    #include<vector>
    #include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<string>
    #include<algorithm>
    #include<cmath>
    #include<stack>
    #include<queue>
    #include<set>
    #define inf 0x3f3f3f3f
    #define mem(a,x) memset(a,x,sizeof(a))
    #define F first
    #define S second
    using namespace std;
    
    typedef long long ll;
    typedef unsigned long long ull;
    typedef pair<int,int> pii;
    
    inline int in()
    {
        int res=0;char c;int f=1;
        while((c=getchar())<'0' || c>'9')if(c=='-')f=-1;
        while(c>='0' && c<='9')res=res*10+c-'0',c=getchar();
        return res*f;
    }
    const int N=10001,MOD=1e9+7;
    
    struct st
    {
        int to;
        int w,t;
    };
    vector<st> G[N];
    int time[N];
    priority_queue<pii,vector<pii>,greater<pii> > q;
    
    bool dijkstra(int lim,int T,int n)
    {
        mem(time,inf);
        time[1]=0;
        q.push(pii(0,1));
        while(!q.empty())
        {
            pii now = q.top();
            q.pop();
            int x=now.S;
            if(time[x] < now.F) continue;
            for(int i=0;i<(int)G[x].size();i++)
            {
                st & t = G[x][i];
                if(t.w>=lim && t.t+time[x] < time[t.to])
                {
                    time[t.to] = t.t+time[x];
                    q.push(pii(time[t.to],t.to));
                }
            }
        }
        //cout<<"time[n]=="<<time[n]<<endl;
        return time[n] <= T;
    }
    int c[N];
    int main()
    {
        int ca=in();
        while(ca--)
        {
            int n=in(),m=in(),T=in();
            int x,y,z,zz,mx=0,mn=inf;
            for(int i=0;i<m;i++)
            {
                scanf("%d%d%d%d",&x,&y,&z,&zz);
                G[x].push_back(st{y,z,zz});
                G[y].push_back(st{x,z,zz});
                mx=max(mx,z);
                mn=min(mn,z);
            }
            int l=mn,r=mx,ans;
            while(l<=r)
            {
                int mid=l+r>>1;
                if(dijkstra(mid,T,n)) l=mid+1,ans=mid;
                else r=mid-1;
            }
            printf("%d\n",ans);
            if(ca) for(int i=0;i<=n;i++) G[i].clear();
        }
        return 0;
    }

[Link 1]: http://acm.hdu.edu.cn/showproblem.php?pid=1839