| ||||||||||
| 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 | |||||||||
水题啊!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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator