51nod 1366 贫富差距（flody）

http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1366

题意：

思路：

如果不是一个连通块的话，肯定是无穷大的。

用floyd求出两两之间的最短路，然后在这些最短路中选最长的*d即可。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<queue>
 5 using namespace std;
 6 const int inf = 0x3f3f3f3f;
 7 
 8 int n,k;
 9 int d[55][55];
10 char mp[55][55];
11 
12 int main()
13 {
14     //freopen("in.txt","r",stdin);
15     int T;
16     scanf("%d",&T);
17     while(T--)
18     {
19         memset(d,0x3f,sizeof(d));
20         scanf("%d%d",&n,&k);
21         for(int i=1;i<=n;i++)
22         {
23             scanf("%s",mp[i]+1);
24             for(int j=1;j<=n;j++)
25             {
26                 if(mp[i][j]=='Y')  d[i][j] = 1;
27             }
28         }
29 
30         for(int k=1;k<=n;k++)
31         {
32             for(int i=1;i<=n;i++)
33             {
34                 for(int j=1;j<=n;j++)
35                 {
36                     d[i][j] = min(d[i][j],d[i][k]+d[k][j]);
37                 }
38             }
39         }
40 
41         int ans = 0;
42         bool flag = true;
43         for(int i=1;i<=n;i++)
44         {
45             if(!flag)  break;
46             for(int j=i+1;j<=n;j++)
47             {
48                 if(d[i][j]==inf)  {flag=false;break;}
49                 ans = max(ans,d[i][j]);
50             }
51         }
52         if(flag)  printf("%d
",ans*k);
53         else puts("-1");
54     }
55     return 0;
56 }