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