Description：

给一个边带权的联通无向图，边集用 $k$ 个集合表示，第 $i$ 个集合内有一些点，这些点之间两两连了一个长为 $v_i$ 的边，求： $$ \sum_{i=1}^n\sum_{j=i}^ndis(i,j) $$ $1\leqslant n\leqslant 10^5,1\leqslant k\leqslant 18$

Solution：

每对点之间最短路可以用 $floyed$ ，但是点数太大，可是团的数量很少，所以可以对团做 $floyed$ ，也就是说先暴力建出团之间的边，然后跑一个 $floyed$ ，这时有： $$ dis(i,j)=\min(d(S_x,S_y)+v_{S_x}+v_{S_y})(i\in S_x,j\in S_y) $$ 那么我们就枚举每个点，把所有团按照 $d(S_x,S_y)+v_{S_x}+v_{S_y}$ 排序，然后依次按顺序加入，每到一个新团，那么他会带来的点就是可以出现在他之中的，但是不出现在它之前的集合中的点的个数，那么我们就可以统计一个 $w[i]$ 表示把 $i$ 看作集合的集合，那么 $w[i]$ 就是只出现在 $i$ 这个集合包含的集合中的点的个数，这个可以用 $FMT$ 快速求出，那么一个团队答案的贡献就是 $w(cur)-w(cur-i)$ ，也就是说 $cur$ 排除了出现在他之前的集合中的点， $w[cur]-w[cur-i]$ 保证了一定出现在 $i$ 中，把这个累加求和就行了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<vector>

#include<cctype>

#include<cstring>

using namespace std;

int n,k;

#define MAXN 100010

#define MAXT 20

int f[MAXT][MAXT];

vector<int> v[MAXN];

int val[MAXT];

int w[1 << MAXT];

int id[MAXT];

int dist[MAXT];

bool cmp_dist(int a,int b){return dist[a] < dist[b];}

int main()

{

	scanf("%d%d",&n,&k);

	for(int i = 1;i <= k;++i)id[i] = i;

	int s,x;

	for(int i = 1;i <= k;++i)

	{

		scanf("%d%d",&val[i],&s);

		for(int j = 1;j <= s;++j)

		{

			scanf("%d",&x);

			v[x].push_back(i);

		}

	}

	for(int i = 1;i <= n;++i)

	{

		int num = 0;

		for(vector<int>::iterator it = v[i].begin();it != v[i].end();++it)

		{

			num |= 1 << (*it - 1);

		}

		++w[num];

	}

	for(int i = 0;i < k;++i)

		for(int j = 0;j < (1 << k);++j)

			if(((j >> i) & 1) == 1)w[j] += w[j ^ (1 << i)];

//	for(int i = 0;i < (1 << k);++i)cout << i << " " << w[i] << endl;

	memset(f,0x3f,sizeof(f));

	for(int i = 1;i <= k;++i)f[i][i] = 0;

	for(int l = 1;l <= n;++l)

		for(int i = 0;i < v[l].size();++i)

			for(int j = 0;j < v[l].size();++j)

				f[v[l][i]][v[l][j]] = min(f[v[l][i]][v[l][j]],val[v[l][i]] + val[v[l][j]]);

	for(int l = 1;l <= k;++l)

		for(int i = 1;i <= k;++i)

			for(int j = 1;j <= k;++j)

				f[i][j] = min(f[i][j],f[i][l] + f[l][j]);

	long long ans = 0;

	for(int i = 1;i <= n;++i)

	{

		memset(dist,0x3f,sizeof(dist));

		for(vector<int>::iterator it = v[i].begin();it != v[i].end();++it)

		{

			for(int j = 1;j <= k;++j)

			{

				dist[j] = min(dist[j],val[*it] + f[*it][j]);

			}

		}

		for(int j = 1;j <= k;++j)dist[j] += val[j];

		sort(id + 1,id + 1 + k,cmp_dist);

		int cur = (1 << k) - 1;

		ans -= dist[id[1]];

		for(int j = 1;j <= k;++j)

		{

			ans += 1ll * dist[id[j]] * (w[cur] - w[cur ^ (1 << (id[j] - 1))]);

			cur ^= 1 << (id[j] - 1);

		}

	}

	cout << ans / 4 << endl;

	return 0;

}