ZR 集训 Day25 – 基础图论

ooliver 发布于 4 小时前 33 次阅读 OI

AI 摘要

台风突袭，上午秒变神秘模拟赛；但基础图论里藏着一招绝活——k个关键点的最短路，用二进制分组加超级源汇，跑20遍Dijkstra就能拿下？

前言

昨天通知今天有台风，所以今天上午改成了神秘模拟赛，题目啥的放最后吧。

P5304 [GXOI/GZOI2019] 旅行者

考虑二进制分组，即枚举 $k$ 个关键点的编号的二进制位，将 $0$、$1$ 分成两个集合，用一个超级源点连向一个集合、用一个超级汇点连向另一个集合，跑最短路即可。由于最终的答案的点对一定有一位上是不一样的，所以这个做法正确性显然。

代码：

C++
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
const int N=1e5+5;

struct graph{
    int n;
    vector<pii> g[N];
    void init(int x){
        n=x;
        for(int i=1;i<=n;i++) g[i].clear();
    }
    void add(int u,int v,int w){
        g[u].push_back({v,w});
    }
    int dij(int s,int t){
        vector<int> dis(n+1,1e18),vis(n+1,0);
        priority_queue<pii> q;
        q.push({0,s});
        dis[s]=0;
        while(q.size()){
            auto[d,u]=q.top();
            q.pop();
            if(vis[u]) continue;
            vis[u]=1;
            for(auto[v,w]:g[u]){
                if(!vis[v]&&dis[u]+w<dis[v]){
                    dis[v]=dis[u]+w;
                    q.push({-dis[v],v});
                }
            }
        }
        return dis[t];
    }
}g;

void solve(){
    int n,m,k,ans=1e18;
    cin>>n>>m>>k;
    vector<int> d(k+1),u(m+1),v(m+1),w(m+1);
    for(int i=1;i<=m;i++) cin>>u[i]>>v[i]>>w[i];
    for(int i=1;i<=k;i++) cin>>d[i];
    for(int j=0;j<=19;j++){
        g.init(n+2);
        for(int i=1;i<=m;i++) g.add(u[i],v[i],w[i]);
        for(int i=1;i<=k;i++){
            if((d[i]>>j)&1) g.add(n+1,d[i],0);
            else g.add(d[i],n+2,0);
        }
        ans=min(ans,g.dij(n+1,n+2));
        g.init(n+2);
        for(int i=1;i<=m;i++) g.add(u[i],v[i],w[i]);
        for(int i=1;i<=k;i++){
            if((d[i]>>j)&1) g.add(d[i],n+1,0);
            else g.add(n+2,d[i],0);
        }
        ans=min(ans,g.dij(n+2,n+1));
    }
    cout<<ans<<"\n";
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int T;
    cin>>T;
    while(T--) solve();
    return 0;
}