hdu1869六度分离(dijkstra)
Problem DescriptionInputOutputSample InputSample Output#include<stdio.h>int map[105][105],node[105],s[105],n,INF=100000000;void set_1(){ for(int i=0;i<n;i++) for(int j=0;j<n;j++) map[i][j]=INF;}void set_2(){ for(int i=0;i<n;i++) { s[i]=0; node[i]=INF; }}int dijkstra(int m){ int min,tm=m,k=1; s[m]=1; node[m]=0; for(int i=2;i<=n;i++) { min=INF; for(int j=0;j<n;j++) if(s[j]==0) { if(node[j]>map[tm][j]+node[tm]) node[j]=map[tm][j]+node[tm]; if(min>node[j]) { min=node[j]; m=j; } } if(s[m]==0) { if(min>7)break;//超出认识的范围，不满足要求跳出 k++; s[m]=1; tm=m; } } if(k==n)//当s集合中有n个人，说明起始的人认识所有的人，反回1 return 1; return 0;}int main(){ int m,a,b; while(scanf("%d%d",&n,&m)>0) { set_1(); while(m--) { scanf("%d%d",&a,&b); map[a][b]=map[b][a]=1; } int i; for( i=0;i<n;i++) { set_2(); if(!dijkstra(i))//如果有一个人不认识所有的人那么就跳出了 break; } printf("%s\n",i==n?"Yes":"No");//当i==n时，说明所有的人都相互认识 }}
