补题：HNU暑期训练第三场-Charles in Charge（二分查找+dijstra（堆优化））

小灰灰 2022-05-16 03:05 146阅读 0赞

题目链接：  
[Charles in Charge][]

题目大意：  
给你n个点，m条边，找出满足点1到点n的路中不超过点1到点n最短路d（1+x%)经过的边的权值最大值最小，输出这个值

解题思路：  
利用二分查找，二分这个最小值，然后利用dijstra算法去检验是否可以找到一条路满足经过的权值不大雨当前的限制，并且求出的最短路不超过d(1+x%),有的话，r=mid；无的话，l=mid+1

AC代码：

#include <iostream>
    #include <cstdio>
    #include <algorithm>
    #include <cstring>
    #include <queue>
    #include <vector>
    
    
    using namespace std;
    
    const long long MAXN = 1e5+7;
    const long long MAXM = 1e5+7;
    const long long INF = 0x7f7f7f7f3f3f3f3f;
    #define ll long long
    
    struct edge{
        int v;
        ll l;
        edge(){}
        edge(int _v, ll _l):v(_v),l(_l){} 
        bool operator <(const edge &e)const
        {
            return e.l < l;
        }
    };
    
    vector<edge> g[MAXN];
    
    ll vis[MAXN],dist[MAXN];
    ll n,m,x;
    
    ll dijstra(ll limit){
        memset(vis,0,sizeof(vis));
        for(int i=1; i<=n; ++i) dist[i] = INF;
    
        priority_queue<edge> pq;
        dist[1] = 0;
        pq.push(edge(1, 0));
        while(!pq.empty()){
            edge tmp = pq.top();
            pq.pop();
            int u = tmp.v;
            if(vis[u]) continue;
            vis[u] = 1;
            for(int j=0; j<g[u].size(); ++j){
                int v = g[u][j].v;
                if(!vis[v] && g[u][j].l <= limit){
                    if(dist[v]>dist[u] + g[u][j].l){
                        dist[v] = dist[u] + g[u][j].l;
                        pq.push(edge(v,dist[v]));
                    }
                }
            }
        }
        return dist[n];
    }
    
    
    int main(){
        cin>>n>>m>>x;
        for(int i=1; i<=m; ++i){
            int u,v;
            ll t;
            cin>>u>>v>>t;
            g[u].push_back(edge(v,t));
            g[v].push_back(edge(u,t));
        }
        ll d = dijstra(INF);
        d = d + d * x / 100;
    
        ll l=0, r = d+233;
        while(l<r){
            ll mid = l+ (r-l) / 2;
            ll ans = dijstra(mid);
            if(ans <= d) r = mid;
            else l = mid+1;
        }
    
        cout<<l<<endl;
        return 0;
    }

[Charles in Charge]: https://cn.vjudge.net/problem/Kattis-charlesincharge