傳送門：
Six Degrees of Cowvin Bacon
題意：
求每頭牛到其他頭牛的最短路徑總和最大者。
思路：
使用floyd-warshall演算法求出每頭牛之間的距離，再統計最大者。
code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
int T,M,N,K,I,a,b,c,ans,cnt;
int dis[301][301], buf[301];
int main(){
cin >> N >> M;
for(int i=1;i<=N;i++)
for(int j=1;j<=N;j++)
dis[i][j] = (i==j?0:(1<<20));
while(M--){
cin >> K;
for(int i=0;i<K;i++) {
cin >> buf[i];
for(int j=0;j<i;j++){
dis[ buf[i] ][ buf[j] ] = 1;
dis[ buf[j] ][ buf[i] ] = 1;
}
}
}
for(int k=1;k<=N;k++)
for(int i=1;i<=N;i++)
for(int j=1;j<=N;j++)
dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
ll tot,mn=(1ll<<40);
for(int i=1;i<=N;i++){
tot = 0;
for(int j=1;j<=N;j++)
tot += dis[i][j];
if(tot<mn) ans = i, mn = tot;
}
cout << mn*100/(N-1) << endl;
}