题目描述
前置知识
二进制拆分
要枚举同一个集合里的两个不同的元素，我们可以将每个元素设一个编号，然后枚举二进制位（或者直接枚举元素），当前位数是 (1) 的放入一个集合，是 (0) 的放入另一个集合，设要枚举的元素为 (x) 和 (y) ，因为 (x ot=y) ，所以它们的二进制肯定有至少一位不同，所以肯定会被枚举到。
超级源与超级汇
这是原来是在网络流里的一些东西，但现在好像成了图论里烂大街的东西。
超级源与超级汇在普通图论中被用来求像一些多起点最短路的问题，其实想一下还是比较简单的，就是将这些点看做一个点（向超级源或超级汇连权值为 (0) 的边）， 然后直接用普通的单源最短路算法就可以求解。
其实在实际应用中，超级源和超级汇主要是一种思想，很多情况下不必把图建出来，直接在初始化单源最短路的时候就可以操作，例如这道题。
思路
二进制拆分
有了上面的前置知识，这道题目就比较简单了，先把 (k) 个点二进制拆分一下，然后每次把两个集合各自连一个超级源，跑两遍堆优化的 (Dijkstra) ，取个 (min) 就可以了，因为是有向图 ，(x->y) 和 (y->x) 的答案不一样，所以要跑两边。
其实超级源不用建出来，直接在初始化的时候将要连接到超级源上的点的 (dis) 赋值为 (0) ，压入优先队列就可以了。
时间复杂度 (Theta(T*n*log_2n*log_2k)) ，需要吸氧。
随机化
我们发现 (n^2) 枚举哪两个点肯定会超时，我们可以和上面的二进制拆分一样，每次随机化将 (k) 个点分为两个集合，然后的操作是一样的。随机个 (20) 次答案正确率就很高了。随机化的好处是容错率高，开始的时候对于两个集合，只是跑了一个集合到另一个集合的，没有反过来，竟然有 (90) 分，还有几次 (100) 分，如果二进制拆分忘了这样的话， (30) 来分走人。
缺点是随机化是要看脸的，虽然概率很低，但万一就过不了呢。
代码
Code 1 二进制拆分
#include<bits/stdc++.h>
#include<queue>
#define one first
#define two second
#define mp make_pair
#define pii pair<ll,int>
#define ll long long
using std::mp;
using std::min;
using std::pair;
using std::vector;
using std::greater;
using std::priority_queue;
const int N=1e5+100,M=5e5+100;
const ll INF=LLONG_MAX-INT_MAX;
struct edge{
int s,e;
ll v;
int net;
}ed[M];
priority_queue<pii,vector<pii>,greater<pii> >q;
int T,n,m,tot,k;
ll minn;
int head[N],point[N];
bool mark[N];
ll dis[N];
inline void clear()
{
tot=0;
memset(head,0,sizeof(head));
return ;
}
inline void add(int s,int e,ll v)
{
ed[++tot]=(edge){s,e,v,head[s]};
head[s]=tot;
return ;
}
inline void Dijkstra()
{
while (!q.empty())
{
pii now=q.top();
q.pop();
if (now.one!=dis[now.two]) continue;
for (int i=head[now.two];i;i=ed[i].net)
if (dis[ed[i].e]>dis[ed[i].s]+ed[i].v)
{
dis[ed[i].e]=dis[ed[i].s]+ed[i].v;
q.push(mp(dis[ed[i].e],ed[i].e));
}
}
return ;
}
inline void check(bool x)
{
for (int j=0;(1<<j)<=k;j++)
{
for (int i=1;i<=n;i++) dis[i]=INF;
for (int i=1;i<=k;i++)
{
bool now=i&(1<<j);
if (now==x)
{
int to=point[i];
dis[to]=0;
q.push(mp(dis[to],to));
mark[i]=1;
}
}
Dijkstra();
for (int i=1;i<=k;i++)
{
if (!mark[i]) minn=min(minn,dis[point[i]]);
mark[i]=0;
}
}
return ;
}
inline void Solve()
{
clear();
minn=INF;
scanf("%d%d%d",&n,&m,&k);
for (int i=1;i<=m;i++)
{
int s,e;ll v;
scanf("%d%d%lld",&s,&e,&v);
add(s,e,v);
}
for (int i=1;i<=k;i++)
scanf("%d",point+i);
check(1);check(0);
printf("%lld
",minn);
return ;
}
int main()
{
scanf("%d",&T);
while (T--) Solve();
return 0;
}
Code 2 随机化
#include<bits/stdc++.h>
#include<queue>
#define one first
#define two second
#define mp make_pair
#define pii pair<ll,int>
#define ll long long
using std::mp;
using std::min;
using std::pair;
using std::vector;
using std::greater;
using std::priority_queue;
const int N=1e5+100,M=5e5+100;
const ll INF=LLONG_MAX-INT_MAX;
struct ios {
inline char gc(){
static const int IN_LEN=1<<18|1;
static char buf[IN_LEN],*s,*t;
return (s==t)&&(t=(s=buf)+fread(buf,1,IN_LEN,stdin)),s==t?-1:*s++;
}
template <typename _Tp> inline ios & operator >> (_Tp&x){
static char ch,sgn; ch = gc(), sgn = 0;
for(;!isdigit(ch);ch=gc()){if(ch==-1)return *this;sgn|=ch=='-';}
for(x=0;isdigit(ch);ch=gc())x=x*10+(ch^'0');
sgn&&(x=-x); return *this;
}
} cin;
struct edge{
int s,e;
ll v;
int net;
}ed[M<<1],id[M];
priority_queue<pii,vector<pii>,greater<pii> >q;
ll minn;
int T,n,m,tot,k;
int head[N],point[N],mark[N],rk[N];
ll dis[N];
inline void clear()
{
tot=0;
for (int i=0;i<=n;i++)
{
mark[i]=0;
head[i]=0;
dis[i]=INF;
}
return ;
}
inline void add(int s,int e,ll v)
{
ed[++tot]=(edge){s,e,v,head[s]};
head[s]=tot;
return ;
}
inline void Dijkstra(int x)
{
while (!q.empty()) q.pop();
dis[x]=0;
q.push(mp(dis[x],x));
while (!q.empty())
{
pii now=q.top();
q.pop();
if (now.one!=dis[now.two]) continue;
for (int i=head[now.two];i;i=ed[i].net)
if (dis[ed[i].e]>dis[ed[i].s]+ed[i].v)
{
dis[ed[i].e]=dis[ed[i].s]+ed[i].v;
q.push(mp(dis[ed[i].e],ed[i].e));
}
}
return ;
}
inline void check(bool x)
{
clear();
for (int i=1;i<=m;i++)
add(id[i].s,id[i].e,id[i].v);
int sz=0;
for (int i=1;i<=k;i++)
if (rk[i]%2==x)
{
add(0,point[i],0);
mark[i]=1;
sz++;
}
if (sz==0) return ;
Dijkstra(0);
for (int i=1;i<=k;i++)
if (!mark[i]) minn=min(minn,dis[point[i]]);
return ;
}
inline void Solve()
{
minn=INF;
cin>>n>>m>>k;
for (int i=1;i<=m;i++)
{
int s,e;ll v;
cin>>s>>e>>v;
id[i]=(edge){s,e,v,0};
}
for (int i=1;i<=k;i++)
cin>>point[i];
int num=20;
while (num--)
{
for (int i=1;i<=k;i++)
rk[i]=rand();
check(1);
check(0);
}
printf("%lld
",minn);
return ;
}
int main()
{
srand(time(NULL));
scanf("%d",&T);
while (T--) Solve();
return 0;
}