Floyd-Warshall模板題，我才剛學最短路。。。。
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> using namespace std; const int maxn=300+50; int d[maxn][maxn]; int v,m,n; int a[maxn]; const int inf=0x3f3f3f3f; void fold() {for(int k=0;k<n;k++)for(int i=0;i<n;i++)for(int j=0;j<n;j++)d[i][j]=min(d[i][j],d[i][k]+d[k][j]); } int main() {scanf("%d%d",&n,&m);memset(d,inf,sizeof(d));for(int i=0;i<n;i++)d[i][i]=0;while(m--){ int t;scanf("%d",&t);for(int i=0;i<t;i++){scanf("%d",&a[i]);a[i]--;}for(int i=0;i<t;i++)for(int j=i+1;j<t;j++)d[a[i]][a[j]]=d[a[j]][a[i]]=1;}fold();int ans=inf;for(int i=0;i<n;i++){ int sum=0;for(int j=0;j<n;j++)sum+=d[i][j];ans=min(ans,sum);}printf("%d\n",100*ans/(n-1));return 0; }
?
)
)
