Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

c++

Posted by 983543692 at 2016-06-14 21:09:24 on Problem 2139
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator