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

水题啊!

Posted by waaao at 2012-12-23 14:05:04 on Problem 1161
rt
#include <cstdio>
#include <algorithm>
using namespace std;
const int MMax=250,NMax=300,LMax=50;
int M,N,L,IN[LMax],circle[NMax],edge[NMax][NMax],G[NMax][NMax];
int next[NMax][MMax];
int main()
{
	scanf("%d%d%d",&M,&N,&L);
	for(int i=1;i<=L;i++) scanf("%d",IN+i);
	for(int i=1;i<=M;i++) for(int j=1;j<=M;j++) G[i][j]=1000000000;
	for(int i=1;i<=M;i++) {
		G[i][i]=0;
		int x;
		scanf("%d",&x);
		for(int j=1;j<=x;j++) {
			scanf("%d",circle+j);
			next[circle[j]][i]=1;
		}
		circle[0]=circle[x];
		for(int j=0;j<x;j++)
			if(edge[circle[j]][circle[j+1]]) G[i][edge[circle[j]][circle[j+1]]]=G[edge[circle[j]][circle[j+1]]][i]=1;
		for(int j=0;j<x;j++) edge[circle[j]][circle[j+1]]=edge[circle[j+1]][circle[j]]=i;
		
	}
	for(int k=1;k<=M;k++)
		for(int i=1;i<=M;i++) 
			for(int j=1;j<=M;j++) if(G[i][k]+G[k][j]<G[i][j])
				G[i][j]=G[i][k]+G[k][j];
	int ret=(~0u>>1),tmp;
	for(int i=1;i<=M;i++) {
		int tot=0;
		for(int j=1;j<=L;j++) {
			int Min=(~0u>>1);
			for(int k=1;k<=M;k++) if(next[IN[j]][k])
				Min=min(Min,G[k][i]);
			//printf("%d\n",Min);
			tot+=Min;
		}
	    if(tot<ret) {
			ret=tot;
			tmp=i;
		}
	}
	printf("%d\n",ret);
	getchar();getchar();
	return 0;
}

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