Six Degrees of Cowvin Bacon POJ 2139(最短路)

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <utility>
 4 #include <cstdio>
 5 #include <cmath>
 6 #include <cstring>
 7 #include <string>
 8 #include <vector>
 9 #include <stack>
10 #include <queue>
11 #include <map>
12 #include <set>
13 
14 using namespace std;
15 typedef long long LL;
16 const int INF_INT=0x3f3f3f3f;
17 const LL INF_LL=0x3f3f3f3f3f3f3f3f;
18 
19 bool es[400][400];
20 int dp[400][400];
21 
22 void add()
23 {
24     int n;
25     cin>>n;
26     int num[400];
27     int cnt=0;
28     for(int i=0;i<n;i++)
29     {
30         int x;
31         scanf("%d",&x);
32         for(int j=0;j<cnt;j++)
33         {
34             es[num[j]][x]=1;
35             es[x][num[j]]=1;
36         }
37         num[cnt++]=x;
38     }
39 }
40 
41 int main()
42 {
43 //    freopen("black.in","r",stdin);
44 //    freopen("black.out","w",stdout);
45     int n,m;
46     cin>>n>>m;
47     for(int i=0;i<m;i++) add();
48 /*    for(int i=1;i<=n;i++)
49         for(int j=1;j<=n;j++)
50         if(es[i][j]) printf("dis %d %d\n",i,j);*/
51     for(int i=1;i<=n;i++)
52         for(int j=1;j<=n;j++)
53         if(es[i][j]) dp[i][j]=1;
54         else dp[i][j]=INF_INT;
55     for(int k=1;k<=n;k++)
56         for(int i=1;i<=n;i++)
57             for(int j=1;j<=n;j++)
58             dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);
59     int ans=INF_INT;
60     for(int i=1;i<=n;i++)
61     {
62         int res=0;
63         for(int j=1;j<=n;j++)
64         if(i!=j) res+=dp[i][j];
65         ans=min(ans,res);
66     }
67     printf("%d\n",ans*100/(n-1));
68     return 0;
69 }