Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
c++#include<iostream> using namespace std; const int maxn=307; const int INF=1<<29; int G[maxn][maxn]; int cow[maxn]; void floyd(int n){ for(int k=1;k<=n;++k) for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) G[i][j]=min(G[i][j],G[i][k]+G[k][j]); } int main() { int n,m;scanf("%d%d",&n,&m); for(int i=1;i<=n;++i) for(int j=1;j<=n;++j)G[i][j]=(i==j)?0:INF; for(int i=1;i<=m;++i){ int k;scanf("%d",&k); for(int j=0;j<k;++j){ scanf("%d",&cow[j]); } for(int j=0;j<k;++j) for(int l=j+1;l<k;++l) G[cow[j]][cow[l]]=1,G[cow[l]][cow[j]]=1; } floyd(n); long long ans=INF; for(int i=1;i<=n;++i) { long long sum=0; for(int j=1;j<=n;++j) if(i!=j)sum+=G[i][j]; ans=min(ans,sum); } cout<<(ans*100/(n-1))<<endl; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator