题目链接：https://jzoj.net/senior/#main/show/6099
考虑直接统计某个点到其它所有点的距离和
我们先把整个团当成一个点建图，处理出任意两个团之间的距离\(dis(i,j)\)，注意这里的\(dis\)表示的是两个不位于团的相交部分的两点之间距离，即路程一定是某个点\(a->相交部分->b->……\)这样的
接下来我们枚举点\(x\)，统计所有点到\(x\)的最短路，我们考虑从\(x\)到所有团的最短路，并按照该最短路从小到大的顺序考虑它们对答案的贡献
对于\(x\)和任意一点\(y\)，其最短路一定是由团之间的距离产生的答案，我们假设\(x\)和\(y\)分别属于联通块\(i,j\)，那么\(dis(i,j)\)想要对答案产生贡献的前提条件就是在集合\(j\)中所有比其小的\(dis\)仍未未出现
即它对答案的贡献就是那些属于当前集合\(j\)中的除了已经计算贡献的点以外的点数
我们记\(cnt[i][sta]\)表示团\(i\)中的点一定存在，\(sta\)中为0的点一定不存在的点的数量
接下来暴力统计答案即可
#include<iostream>
#include<string.h>
#include<string>
#include<stdio.h>
#include<algorithm>
#include<math.h>
#include<vector>
#include<queue>
#include<bitset>
#include<map>
#include<set>
using namespace std;
#define lowbit(x) (x)&(-x)
#define rep(i,a,b) for (int i=a;i<=b;i++)
#define per(i,a,b) for (int i=a;i>=b;i--)
#define maxd 1000000007
typedef long long ll;
const int N=100000;
const double pi=acos(-1.0);
int n,m,cost[20],in[100100],id[20];
ll dis[20][20],cnt[20][1<<20],all,sum[1<<20],d[20];
bitset<100100> block[20];
int read()
{
int x=0,f=1;char ch=getchar();
while ((ch<'0') || (ch>'9')) {if (ch=='-') f=-1;ch=getchar();}
while ((ch>='0') && (ch<='9')) {x=x*10+(ch-'0');ch=getchar();}
return x*f;
}
bool cmp(int x,int y)
{
return d[x]<d[y];
}
void init()
{
n=read();m=read();all=(1<<m)-1;
rep(i,1,m)
{
cost[i]=read();int len=read();
rep(j,1,len)
{
int x=read();
in[x]|=(1<<(i-1));
block[i][x]=1;
}
}
rep(i,1,n) sum[in[i]]++;
rep(i,1,m)
{
rep(j,0,all) if (j&(1<<(i-1))) cnt[i][j]=sum[j];
rep(j,1,m)
{
rep(k,0,all)
{
if (k&(1<<(j-1))) cnt[i][k]+=cnt[i][k^(1<<(j-1))];
}
}
}
}
void floyd()
{
rep(i,1,m) rep(j,1,m) dis[i][j]=dis[j][i]=maxd;
rep(i,1,m) dis[i][i]=cost[i];
rep(i,1,m)
{
rep(j,1,m)
{
if (i==j) continue;
if ((block[i]&block[j]).any()) {dis[i][j]=cost[i]+cost[j];dis[j][i]=dis[i][j];}
}
}
rep(k,1,m)
{
rep(i,1,m)
{
rep(j,1,m)
{
if ((k==i) || (k==j) || (i==j)) continue;
ll nowdis=dis[i][k]+dis[k][j];
if ((k!=i) && (k!=j)) nowdis-=cost[k];
dis[i][j]=min(nowdis,dis[i][j]);
}
}
}
}
void work()
{
ll ans=0;
rep(i,1,n)
{
rep(j,1,m) {id[j]=j;d[j]=maxd;}
rep(j,1,m)
{
if (in[i]&(1<<(j-1)))
{
rep(k,1,m) d[k]=min(d[k],dis[j][k]);
}
}
sort(id+1,id+1+m,cmp);
int sta=0;
rep(j,1,m)
{
ans+=d[id[j]]*cnt[id[j]][all^sta];
sta|=(1<<(id[j]-1));
}
ans-=d[id[1]];
}
printf("%lld",ans/2);
}
void file()
{
freopen("dist.in","r",stdin);
freopen("dist.out","w",stdout);
}
int main()
{
file();
init();
floyd();
work();
return 0;
}