经典题 图论（没什么说的）

源代码：

• Source Code

  #include <iostream>
  #include <math.h>
  #define INF 0xffffff
  int citytocity[251][251]={0};
  int region[201][201];
  int cityinregion[251][201]={0};
  int club[31]={0};
  
  using namespace std;
  int main()
  {
      int m;
      cin >>m;
                int s,n,temp,becity,afcity,fisrt;
                cin >>n>>s;
                for(int i=0;i<s;i++)
                   cin >>club[i];
                for( i=0;i<=m;i++)
                 for(int j=0;j<=m;j++)
                 {
                         if(i==j)   region[i][j]=0;
                         else   region[i][j]=INF;
                         }
                 for( i=1;i<=m;i++)
                 {
                                 cin >>temp;
                                 cin >>becity;
                                 fisrt=becity;
                                 cityinregion[becity][i]=1;
                                 for(int j=1;j<temp;j++)
                                 {
                                         cin >>afcity;
                                         cityinregion[afcity][i]=1;
                                         if(citytocity[becity][afcity]>0)
                                         {
                                              region[citytocity[becity][afcity]][i]=1;
                                              region[i][citytocity[becity][afcity]]=1;
                                         }
                                         else    {
                                                 citytocity[becity][afcity]=i;
                                                 citytocity[afcity][becity]=i;
                                                 }
                                 becity=afcity;
                                 }
                                         if(citytocity[afcity][fisrt]>0)
                                         {
                                              region[citytocity[afcity][fisrt]][i]=1;
                                              region[i][citytocity[afcity][fisrt]]=1;
                                              }
                                         else {
                                              citytocity[afcity][fisrt]=i;
                                              citytocity[fisrt][afcity]=i;
                                              }
                 }
                 
                 for(int k=1;k<=m;k++)
                   for(int i=1;i<=m;i++)
                   for(int  j=1;j<=m;j++)
                   {
                            if(region[i][j]>(region[i][k]+region[k][j]))
                              region[i][j]=region[i][k]+region[k][j];
                              }
      
            int minm=INF;
            for(i=1;i<=m;i++)
             {
                            int sum=0;
                            for(int j=0;j<s;j++)
                            {
                                    int mins=INF;
                                    for(int k=1;k<=m;k++)
                                    {
                                            if(cityinregion[club[j]][k]!=0)
                                              {
                                                if(mins>region[k][i])
                                                      mins=region[k][i];
                                                }
                                    }
                                    sum+=mins;
                            }
                if(minm>sum)
                    minm=sum;
                }
             
            cout <<minm<<endl;
            return 0;
  }