where
題意
雙向邊，問以某隻牛為起點，到其他牛的最短路徑的總和後，取平均（不包含自己）乘上100。
思考
無起點，無終點，又要每個到每個的，所以思考下 Floyd-Warshall。
| Floyd-Warshall 複雜度為 O( | V | ^3) 。 |
題目說最多有300隻牛，所以還可。
Code
#include <iostream>
#include <cstring>
using namespace std;
int T, N, M, Q, dp[305][305], arr[305];
void ini(void){
int i, j;
scanf("%d %d", &N, &M);
//初始化
memset(dp, 127, sizeof(dp));
for(i = 1; i <= N; i++){
dp[i][i] = 0;
}
//每個電影
while(M--){
scanf("%d", &Q);
for(i = 0; i < Q; i++) scanf("%d", arr + i);
//將邊連起
for(i = 0; i < Q; i++){
for(j = i + 1; j < Q; j++){
dp[ arr[i] ][ arr[j] ] = dp[ arr[j] ][ arr[i] ] = 1;
}
}
}
}
void sol(void){
int i, j, k;
//Floyd-Warshall
for(k = 1; k <= N; k++){
for(i = 1; i <= N; i++){
for(j = 1; j <= N; j++){
dp[i][j] = min(dp[i][k] + dp[k][j], dp[i][j]);
}
}
}
//get answers
for(i = 1, T = 2147483640; i <= N; i++){
for(j = 1, k = 0; j <= N; j++) k += dp[i][j];
T = min(k, T);
}
//被坑的地方
cout<<100 * T / (N - 1)<<endl;
}
int main(void){
int i, j;
ini();
sol();
}
被坑點
100 * (T / (N - 1))
會先變成 int 再去乘上100
但若是
100 * T / (N - 1)
會變成 100 * T 的 int 再去除上 (N - 1) 為小數