zcmimi's blog
查看原题

点击跳转

传统解法

暴力的思路是求出k个点两两之间最短路径

我们可以按二进制逐位对k个点染色(该位为1染为黑色,否则染为白色)

每次求出黑点到白点的最短距离,更新答案

这样可以保证k点中每对点 至少有一次被分别染色为黑和白

复杂度n \log n \log k

#include<bits/stdc++.h>
typedef long long ll;
const int N=100011,M=500011;
int n,m,k,a[N],cnt,head[N];
ll d[N],ans;
struct edge{int to,nxt,w;}e[M];
void add(int x,int y,int w){e[++cnt].to=y,e[cnt].nxt=head[x],head[x]=cnt,e[cnt].w=w;}
#define fl(i,x) for(int i=head[x],to;to=e[i].to,i;i=e[i].nxt)
struct node{
    int x;ll d;
    bool operator<(const node&t)const{return d>t.d;}
};
bool vis[N];
std::priority_queue<node>q;
void dij(int t){
    for(int i=1;i<=n;++i)d[i]=-1ull>>1;
    memset(vis,0,sizeof vis);
    for(int i=1;i<=k;++i)if(i&t)
        q.push((node){a[i],d[a[i]]=0});
    while(!q.empty()){
        int x=q.top().x;q.pop();
        if(vis[x])continue;
        vis[x]=1;
        fl(i,x)if(d[x]+e[i].w<d[to])
            q.push((node){to,d[to]=d[x]+e[i].w});
    }
    for(int i=1;i<=k;++i)if(!(i&t))
        if(d[a[i]]<ans)ans=d[a[i]];
}
void solve(){
    scanf("%d%d%d",&n,&m,&k);
    int x,y,w;
    memset(head,0,sizeof head);cnt=0;
    for(int i=1;i<=m;++i)
        scanf("%d%d%d",&x,&y,&w),add(x,y,w);
    for(int i=1;i<=k;++i)scanf("%d",a+i);
    ans=-1ull>>1;
    for(int i=log2(k);~i;--i)dij(1<<i);
    printf("%lld\n",ans);
}
int main(){
    int T;scanf("%d",&T);
    while(T--)solve();
}

解法二

对每个点,求出能到达它的最近的感兴趣的城市f_i,距离设为a_i

与它能到达的离它最近的感兴趣的城市g_i,距离设为b_i

那么每条边(u,v,w)的贡献就是a_u+w+b_v,用这个值更新答案即可

复杂度n\log n

#include<bits/stdc++.h>
typedef long long ll;
const int N=100011,M=500011;
int n,m,k,a[N],u[M],v[M],w[M],cnt,head[N],f[N],g[N];
ll c[N],d[N];
struct edge{int to,nxt,w;}e[M];
void add(int x,int y,int w){e[++cnt].to=y,e[cnt].nxt=head[x],head[x]=cnt,e[cnt].w=w;}
#define fl(i,x) for(int i=head[x],to;to=e[i].to,i;i=e[i].nxt)
struct node{
    int x;ll d;
    bool operator<(const node&t)const{return d>t.d;}
};
bool vis[N];
void dij(bool opt){
    std::priority_queue<node>q;
    for(int i=1;i<=n;++i)d[i]=-1ull>>1;
    memset(vis,0,sizeof vis);
    memset(f,0,sizeof f);
    memset(head,0,sizeof head);cnt=0;
    for(int i=1;i<=m;++i)
        if(opt)add(v[i],u[i],w[i]);
        else add(u[i],v[i],w[i]);
    for(int i=1;i<=k;++i)
        f[a[i]]=a[i],
        q.push((node){a[i],d[a[i]]=0});
    while(!q.empty()){
        int x=q.top().x;q.pop();
        if(vis[x])continue;
        vis[x]=1;
        fl(i,x)if(d[x]+e[i].w<d[to])
            f[to]=f[x],
            q.push((node){to,d[to]=d[x]+e[i].w});
    }
}
void cmin(ll&x,ll y){if(y<x)x=y;}
void solve(){
    memset(c,0,sizeof c);
    memset(g,0,sizeof g);
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=m;++i)scanf("%d%d%d",u+i,v+i,w+i);
    for(int i=1;i<=k;++i)scanf("%d",a+i);
    dij(0);
    for(int i=1;i<=n;++i)
        c[i]=d[i],g[i]=f[i];
    dij(1);
    ll ans=-1ull>>1;
    for(int i=1;i<=m;++i)
        if(g[u[i]]&&f[v[i]]&&g[u[i]]!=f[v[i]])
            cmin(ans,c[u[i]]+d[v[i]]+w[i]);
    printf("%lld\n",ans);
}
int main(){
    int T;scanf("%d",&T);
    while(T--)solve();
}
LOJ 3087「GXOI or GZOI2019」旅行者
comment评论
Search
search