题意：给出n，m和k，表示有n个细菌，m种仪器和k种细菌，给出k种细菌的数量ci，然后每个细菌按照种类排成一排（所以有第i种细菌的序号从∑（1≤j≤i-1）cj + 1 到∑（1≤j≤i）cj）；接下来给出m种仪器，有u，v，x三个值，表示说从可以在第u，v号细菌之间移动能量，代价为x。请帮助判断说这些细菌是否正确，正确的前提条件是说同种细菌之间移动能量为0，如果正确的话，给出两两细菌（种类）间移动能量的最小值。
思路：并差集+floyd；
#include <cstdio>
#include <cstring>
#include <algorithm>
#define maxn 100010
using namespace std;
const int inf=<<; int n,m,k;
int g[][];
int c[maxn];
int f[maxn],u[maxn],v[maxn],x[maxn];
int num[maxn];
int xx[maxn];
int sum[maxn]; int Find(int x)
{
if(x==f[x]) return x;
return f[x]=Find(f[x]);
} int main()
{
while(scanf("%d%d%d",&n,&m,&k)!=EOF)
{
int fx,fy;
for(int i=; i<=k; i++)
{
scanf("%d",&c[i]);
sum[i]=sum[i-]+c[i];
}
for(int i=; i<=n; i++)
{
f[i]=i;
}
for(int i=; i<=k; i++)
{
for(int j=sum[i-]+; j<=sum[i]; j++)
{
xx[j]=i;
}
}
for(int i=; i<=m; i++)
{
scanf("%d%d%d",&u[i],&v[i],&x[i]);
int uu=u[i],vv=v[i];
if(uu>vv) swap(uu,vv);
fx=Find(uu);
fy=Find(vv);
if(x[i]==)
{
if(fx!=fy)
{
f[fy]=fx;
}
}
}
bool flag=false;
for(int i=; i<=k; i++)
{
int x=Find(sum[i-]+);
int cnt=;
for(int j=sum[i-]+; j<=sum[i]; j++)
{
if(Find(j)==x) cnt++;
}
if(cnt!=c[i])
{
flag=true;
break;
}
}
if(flag)
{
printf("No\n");
}
else
{
for(int i=; i<=k; i++)
{
for(int j=; j<=k; j++)
{
if(i==j) g[i][j]=;
else g[i][j]=inf;
}
}
for(int i=; i<=m; i++)
{
g[xx[u[i]]][xx[v[i]]]=min(g[xx[u[i]]][xx[v[i]]],x[i]);
g[xx[v[i]]][xx[u[i]]]=min(g[xx[v[i]]][xx[u[i]]],x[i]);
}
for(int c=; c<=k; c++)
{
for(int i=; i<=k; i++)
{
if(i==c)continue;
for(int j=; j<=k; j++)
{
if(i==j||j==c) continue;
g[i][j]=min(g[i][j],g[i][c]+g[c][j]);
}
}
}
printf("Yes\n");
for(int i=; i<=k; i++)
{
for(int j=; j<=k; j++)
{
if(g[i][j]==inf&&i!=j)
{
printf("-1 ");
}
else printf("%d ",g[i][j]);
}
printf("\n");
}
}
}
return ;
}