[题目传送门](https://www.luogu.org/problem/CF400D)
直接用并查集把边权为0的两个点合并起来,然后看看同一个type的点是否在同一个集合中,最后在每个type之间建边,跑一遍Floyd即可。
代码:
``` cpp
#include<bits/stdc++.h>
inline int read(){int x=0;char c=getchar();while(c<'0' || c>'9')c=getchar();while(c>='0' && c<='9')x=(x<<3)+(x<<1)+(c^'0'),c=getchar();return x;}
int n,m,k,c[501],fa[100001],id[100001],dis[501][501],cnt;
struct sb{int a,b,c;}e[100001];
inline int find(const int &x){return fa[x]==x?x:fa[x]=find(fa[x]);}//并查集
inline bool cmp(const sb &a,const sb &b){return a.c<b.c;}
signed main()
{
n=read(),m=read(),k=read();
for(register int i=1;i<=n;i++)fa[i]=i;//并查集初始化
for(register int i=1;i<=k;i++)c[i]=read();
for(register int i=1;i<=m;i++)e[i].a=read(),e[i].b=read(),e[i].c=read();
std::sort(e+1,e+m+1,cmp);
for(register int i=1;i<=m;i++)
{
if(e[i].c>0)break;
fa[find(e[i].a)]=find(e[i].b);//合并
}
for(register int i=1;i<=k;i++)
{
int x=find(cnt+1);
id[cnt+1]=i;
for(register int j=cnt+2;j<=cnt+c[i];j++){id[j]=i;if(find(j)!=x){printf("No");return 0;}}//判断是否在一个集合中
cnt+=c[i];
}
for(register int i=1;i<=k;i++)for(register int j=1;j<=k;j++)if(i!=j)dis[i][j]=1000000000;//Floyd初始化
for(register int i=1;i<=m;i++)dis[id[e[i].b]][id[e[i].a]]=dis[id[e[i].a]][id[e[i].b]]=std::min(dis[id[e[i].a]][id[e[i].b]],e[i].c);//建边
for(register int l=1;l<=k;l++)for(register int i=1;i<=k;i++)for(register int j=1;j<=k;j++)dis[i][j]=std::min(dis[i][j],dis[i][l]+dis[l][j]);//Floyd
printf("Yes\n");
for(register int i=1;i<=k;i++){for(register int j=1;j<=k;j++)printf("%d ",dis[i][j]==1000000000?-1:dis[i][j]);printf("\n");}
}
```
![](https://www.luogu.org/images/congratulation.png)