codeforces 400 D Dima and Bacteria【并查集 Floyd】

题意：给出n个点，分别属于k个集合，判断每个集合里面的点的距离都为0，为0的话输出yes,并输出任意两个集合之间的最短路

这道题目有两个地方不会处理，

先是n个点，分别属于k个集合，该怎么记录下来这里，

然后就是判断每个集合里面的点的距离是否为1，这里可以用并查集来做，如果在输入点的时候，距离为0，就将这两点合并

最后判断每个点，如果他们同属于一个集合，判断它俩的根是否一样就可以了

最后用floyd求最短路

#include<iostream>  
#include<cstdio>  
#include<cstring> 
#include <cmath> 
#include<stack>
#include<vector>
#include<map> 
#include<set>
#include<queue> 
#include<algorithm>  
using namespace std;

#define foreach(i,c) for (__typeof(c.begin()) i = c.begin(); i != c.end(); ++i)

typedef long long LL;
const int INF = (1<<30)-1;
const int mod=1000000007;
const int maxn=1005;

int in[maxn*maxn],d[maxn][maxn],p[maxn*maxn];

int find(int x){ return x==p[x]? x:p[x]=find(p[x]);}

int main(){
    int n,m,k;    
    scanf("%d %d %d",&n,&m,&k);
    int sum=0;
    for(int i=1;i<=k;i++){
        int c;
        cin>>c;
        for(int j=sum+1;j<=sum+c;j++) in[j]=i;    
        sum+=c;        
    }
    
    for(int i=1;i<=k;i++){//��ʼ��floyed���� 
        for(int j=1;j<=k;j++){
            if(i==j) d[i][j]=0;
            else d[i][j]=INF;
        }        
    }
    for(int i=1;i<=n;i++) p[i]=i;
    
    while(m--){
        int u,v,w;
        cin>>u>>v>>w;
        if(in[u]!=in[v]&&d[in[u]][in[v]]>w) d[in[u]][in[v]]=d[in[v]][in[u]]=w;
        
        if(w==0){
            int x=find(u);
            int y=find(v);
            if(x!=y) p[x]=y;
        }
    }
    
    for(int i=2;i<=n;i++){
        if(in[i]==in[i-1]){
            int x=find(i);
            int y=find(i-1);
            if(x!=y){        //�������ͬһ�����ϵ��Ǹ���ͬ��˵������֮��ķ��ò���0�����NO 
                printf("No
");
                return 0;
            }
        }
    }
    printf("Yes
");
    
    for(int p=1;p<=k;p++)
     for(int i=1;i<=k;i++)
      for(int j=1;j<=k;j++)
      d[i][j]=min(d[i][j],d[i][p]+d[p][j]);
      
      for(int i=1;i<=k;i++){
          for(int j=1;j<=k;j++){
              if(d[i][j]==INF) printf("-1 ");
              else printf("%d ",d[i][j]);
            }
          printf("
");
      }
      
      return 0;
}