http://acm.pku.edu.cn/JudgeOnline/problem?id=1161
Код:
#include "iostream" #include "string.h" #define INF 100000000 using namespace std; int main(){ int FreeLand[201][201], City[251][251], Club[31], AdjacentLand[251][201]; int m,n,l; int i,j,k,curr,first,temp,last,min,sum,place; cin>>m>>n>>l; for (i=0;i<l;i++) cin>>Club[i]; for (i=0;i<m;i++) for (j=0;j<m;j++) if (j==i) FreeLand[i][j]=0; else FreeLand[i][j]=INF; memset(City,0,sizeof(City)); memset(AdjacentLand,0,sizeof(AdjacentLand)); for (i=0;i<m;i++){ cin>>temp; cin>>first; last=first; AdjacentLand[first][i]=1; for (j=1;j<temp;j++){ cin>>curr; AdjacentLand[curr][i]=1; if (City[last][curr]>0) FreeLand[City[last][curr]-1][i]=FreeLand[i][City[last][curr]-1]=1; else City[last][curr]=City[curr][last]=i+1; last=curr;} if (City[last][first]>0) FreeLand[City[last][first]-1][i]=FreeLand[i][City[first][last]-1]=1; else City[last][first]=City[first][last]=i+1; } for (k=0;k<m;k++) for (i=0;i<m;i++) for (j=0;j<m;j++) if (FreeLand[i][k]+FreeLand[k][j]<FreeLand[i][j]) FreeLand[i][j]=FreeLand[i][k]+FreeLand[k][j]; min=INF; for (i=0;i<m;i++){ sum=0; for (j=0;j<l;j++){ temp=INF; for (k=0;k<m;k++){ if (AdjacentLand[Club[j]][k]==0) continue; if (temp>FreeLand[k][i]) temp=FreeLand[k][i];} sum+=temp;} if (min>sum){ min=sum; place=i;} } cout<<min<<endl; }