洛谷5304 [GXOI/GZOI2019]旅行者

题意

给出一个 $N$ 点 $M$ 边的有向图，以及 $K$ 个感兴趣的点，求感兴趣的点两两之间最短路的最小值。

$N\le 100000 \ , \ M\le 500000$ 。

题解

如果建立原点和汇点，把 $K$ 个点分成两组，分别与原点汇点相连，再从原点开始跑到汇点的最短路就是最小值。

但这样显然无法涵盖所有情况。所以枚举二进制位，把当前位为 $1$ 的加入第一组，其它的放入第二组。因为两个数至少有一个二进制位不同，所以这样可以涵盖所有情况。

多测不清空，爆零两行泪。

#include<bits/stdc++.h>
#define ll long long
#define mp make_pair
#define pii pair<ll,ll>

using namespace std;

inline ll read()
{
    char ch=getchar(); ll f=1,x=0;
    while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
    while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
    return f*x;
}

struct Edge {
    ll next,to,w;
} edge[700005],edge2[700005];
const ll MAXN=100005;
bool vis[MAXN];
ll cnt,cnt2,head[MAXN],head2[MAXN],t,n,m,k,a,b,c,st,ed,dis[MAXN],s[MAXN];

inline void add(ll u,ll v,ll w)
{
    edge[++cnt].to=v;
    edge[cnt].w=w;
    edge[cnt].next=head[u];
    head[u]=cnt;
}

inline ll dijkstra()
{
    priority_queue <pii,vector<pii>,greater<pii> > q;
    memset(vis,0,sizeof(vis));
    memset(dis,0x3f,sizeof(dis));
    dis[st]=0;
    q.emplace(mp(0,st));
    while (!q.empty())
    {
        ll x=q.top().second; q.pop();
        if (vis[x]) continue;
        vis[x]=1;
        for (ll i=head[x];i;i=edge[i].next)
        {
            ll y=edge[i].to,w=edge[i].w;
            if (dis[x]+w<dis[y])
            {
                dis[y]=dis[x]+w;
                q.emplace(mp(dis[y],y));
            }
        }
    }
    return dis[ed];
}

inline void init()
{
    cnt=0;
    memset(head,0,sizeof(head));
}

signed main()
{
    t=read();
    while (t--)
    {
        init();
        n=read(); m=read(); k=read();
        st=n+1; ed=n+2;
        for (ll i=1;i<=m;i++)
        {
            a=read(); b=read(); c=read();
            add(a,b,c);
        }
        for (ll i=1;i<=k;i++) s[i]=read();
        cnt2=cnt;
        memcpy(edge2,edge,sizeof(edge));
        memcpy(head2,head,sizeof(head));
        ll ans=1e18;
        for (ll i=0;(1<<i)<=k;i++)
        {
            for (ll j=1;j<=k;j++)
            {
                if (j>>i&1) add(st,s[j],0);
                else add(s[j],ed,0);
            }
            ans=min(ans,dijkstra());
            cnt=cnt2;
            memcpy(edge,edge2,sizeof(edge));
            memcpy(head,head2,sizeof(head));
            for (ll j=1;j<=k;j++) //交换两组的顺序再来一次
            {
                if (j>>i&1) add(s[j],ed,0);
                else add(st,s[j],0);
            }
            ans=min(ans,dijkstra());
            cnt=cnt2;
            memcpy(edge,edge2,sizeof(edge));
            memcpy(head,head2,sizeof(head));
        }
        printf("%lld\n",ans);
    }
    return 0;
}