小铭铭最近进入了某情报部门，该部门正在被如何建立安全的通道连接困扰。

第一行包含三个整数 n;m;p，表示情报站的数量，可以建立的通道数量和重要情报站的数

输出一行一个整数，表示任意相同频道的情报站之间都建立通道连接所花费的最少资源总量。

选择 (1; 5); (3; 5); (2; 5); (4; 5) 这 4 对情报站连接。

  1 #include<iostream>  2 #include<algorithm>  3 #include<cstring>  4 #include<cstdio>  5 #include<cmath>  6 #include<vector>  7 #include<queue>  8 using namespace std;  9 const int INF=0x3f3f3f3f; 10 const int mxn=3005; 11 int read(){ 12     int x=0,f=1;char ch=getchar(); 13     while(ch<‘0‘ || ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 14     while(ch>=‘0‘ && ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} 15     return x*f; 16 } 17 struct edge{ 18     int v,nxt,w; 19 }e[mxn<<1]; 20 int hd[mxn],mct=0; 21 void add_edge(int u,int v,int w){ 22     e[++mct].v=v;e[mct].nxt=hd[u];e[mct].w=w;hd[u]=mct;return; 23 } 24 int n,m,p; 25 int f[1001][1<<10]; 26 int st[mxn],top=0; 27 bool inq[mxn]; 28 queue<int>q; 29 void SPFA(int S){ 30     while(!q.empty()){ 31         int u=q.front();q.pop();inq[u]=0; 32         for(int i=hd[u];i;i=e[i].nxt){ 33             int v=e[i].v; 34             if(f[v][S]>f[u][S]+e[i].w){ 35                 f[v][S]=f[u][S]+e[i].w; 36                 if(!inq[v]){ 37                     inq[v]=1; 38                     q.push(v); 39                 } 40             } 41         } 42     } 43     return; 44 } 45 int g[1<<11],dp[1<<11]; 46 vector<int>col[12]; 47 bool vis[mxn]; 48 int ED=0; 49 int STN(){ 50     int i,ed=1<<top; 51     for(int S=1;S<ed;S++){ 52         for(i=0;i<n;i++){ 53             for(register int tmp=(S-1)&S;tmp;tmp=(tmp-1)&S) 54                 f[i][S]=min(f[i][S],f[i][tmp]+f[i][S^tmp]); 55             if(f[i][S]<INF){q.push(i);inq[i]=1;} 56         } 57         SPFA(S); 58     } 59     int res=INF; 60     for(i=0;i<n;i++)res=min(res,f[i][ed-1]); 61     return res; 62 } 63 void calc(){ 64     for(int S=1;S<=ED;S++){//枚举把哪些频道连在一起  65         if((S&ED)==S){ 66             int tmp=S,th=0; 67             top=0; 68             memset(f,0x3f,sizeof f); 69             while(tmp){ 70                 if(tmp&1){ 71                     for(int i=0;i<col[th].size();i++) 72                         f[col[th][i]][1<<top]=0,st[top++]=col[th][i]; 73                 } 74                 th++; 75                 tmp>>=1; 76             } 77             g[S]=STN(); 78         } 79     } 80     return; 81 } 82 void solve(){ 83     for(int S=1;S<=ED;S++){ 84         if((S&ED)==S){ 85             dp[S]=g[S]; 86             for(int i=(S-1)&S;i;i=(i-1)&S){ 87                 dp[S]=min(dp[S],dp[i]+dp[S-i]); 88             } 89         } 90     } 91     return; 92 } 93 int main(){ 94     int i,u,v,w; 95     n=read();m=read();p=read(); 96     for(i=1;i<=m;i++){ 97         u=read()-1;v=read()-1;w=read(); 98         add_edge(u,v,w); 99         add_edge(v,u,w);100     }101     int c,d;102     for(i=1;i<=p;i++){103         c=read()-1;d=read()-1;104         col[c].push_back(d);105     }106     for(i=0;i<p;i++)if(col[i].size())ED|=(1<<i);107     calc();108     solve();109     printf("%d\n",dp[ED]);110     return 0;111 }