题解
我们先跑一个斯坦纳树出来
斯坦纳树是什么，是一个包含点集里的点联通所需要的最小的价值，显然他们联通的方式必然是一棵树
我们可以设一个状态为(dis[i][S])表示以第i个点为根，点集为(S)的点联通所需要的最小价值
我们可以从小到大枚举(S)
有两种更新方法
(dis[i][S] = min(dp[j][S] + w(i,j),dis[i][S]))
(dis[i][S] = min(dis[i][T] + dis[i][S oplus T],dis[i][S]))
我们只要从小到大枚举S的时候，同时枚举S的所有子集，然后在当前的S跑一遍最短路即可，初始状态是把所有的最短路非正无穷的点扔进队列
之后我们设一个颜色集(T)联通所需要的最小价值是(f[T])
我们只要在将T包含的所有点集的二进制表示找出来，找(dis[i][S])最小的即可
由于是一个斯坦纳树森林，我们对于(f[T])再进行子集枚举，更新一遍即可
(f[T] = min(f[T],f[W] + f[T oplus W]))
代码
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define enter putchar('
')
#define space putchar(' ')
#define MAXN 1005
//#define ivorysi
using namespace std;
typedef long long int64;
typedef long double db;
typedef unsigned int u32;
template<class T>
void read(T &res) {
res = 0;char c = getchar();T f = 1;
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
res = res * 10 + c - '0';
c = getchar();
}
res *= f;
}
template<class T>
void out(T x) {
if(x < 0) {putchar('-');x = -x;}
if(x >= 10) out(x / 10);
putchar('0' + x % 10);
}
int N,M,P;
struct node {
int to,next,val;
}E[MAXN * 10];
int sumE,head[MAXN],C[15],dis[MAXN][(1 << 10) + 5],id[MAXN],g[(1 << 10) + 5],f[(1 << 10) + 5],all;
bool inq[MAXN];
void add(int u,int v,int c) {
E[++sumE].to = v;
E[sumE].next = head[u];
E[sumE].val = c;
head[u] = sumE;
}
queue<int> Q;
void spfa(int S) {
while(!Q.empty()) {
int u = Q.front();Q.pop();
inq[u] = 0;
for(int i = head[u] ; i ; i = E[i].next) {
int v = E[i].to;
if(dis[v][S] > dis[u][S] + E[i].val) {
dis[v][S] = min(dis[u][S] + E[i].val,dis[v][S]);
if(!inq[v]) {Q.push(v);inq[v] = 1;}
}
}
}
}
void Init() {
read(N);read(M);read(P);
int u,v,w;
for(int i = 1 ; i <= M ; ++i) {
read(u);read(v);read(w);
add(u,v,w);add(v,u,w);
}
int c,d;
for(int i = 1 ; i <= P ; ++i) {
read(c);read(d);
id[d] = i;
C[c] |= 1 << i - 1;
all |= 1 << c - 1;
}
for(int i = 1 ; i <= N ; ++i) {
for(int j = 0 ; j < (1 << P) ; ++j) dis[i][j] = 0x7fffffff;
if(id[i]) dis[i][1 << (id[i] - 1)] = 0;
dis[i][0] = 0;
}
}
void Solve() {
for(int S = 1 ; S < (1 << P) ; ++S) {
for(int T = (S - 1) & S ; T ; T = (T - 1) & S) {
for(int i = 1 ; i <= N ; ++i) {
if(dis[i][T] >= 0x7fffffff || dis[i][S ^ T] >= 0x7fffffff) continue;
dis[i][S] = min(dis[i][S],dis[i][T] + dis[i][S ^ T]);
}
}
for(int i = 1 ; i <= N ; ++i) {
inq[i] = 0;
if(dis[i][S] < 0x7fffffff) {Q.push(i);inq[i] = 1;}
}
spfa(S);
g[S] = 0x7fffffff;
for(int i = 1 ; i <= N ; ++i) g[S] = min(g[S],dis[i][S]);
}
for(int T = all ; T ; T = (T - 1) & all) {
int S = 0;
for(int i = 1 ; i <= P ;++i) {
if(T >> (i - 1) & 1) S |= C[i];
}
f[T] = g[S];
}
for(int S = 1 ; S <= all ; ++S) {
for(int T = (S - 1) & S; T ; T = (T - 1) & S) {
f[S] = min(f[S],f[S ^ T] + f[T]);
}
}
out(f[all]);enter;
}
int main() {
#ifdef ivorysi
freopen("f1.in","r",stdin);
#endif
Init();
Solve();
}