Source Code

Problem: 1161  User: yzhw 
Memory: 732K  Time: 79MS 
Language: G++  Result: Accepted 

Source Code 
# include <iostream>
# include <queue>
# include <cstring>
# include <vector>
using namespace std;
int n,m;
int pn,pos[31],len[201];
bool used[201];
vector<int> face[201];
vector<int> graph[201];
vector<int> target[31];
inline int min(int a,int b)
{
   return a<b?a:b;
}
void bfs(int ori)
{
   memset(used,0,sizeof(used));
   len[ori]=0;
   queue<int> q;
   q.push(ori);
   while(!q.empty())
   {
      int now=q.front();
      q.pop();
      used[now]=1;
      for(int i=0;i<graph[now].size();i++)
        if(!used[graph[now][i]])
        {
          used[graph[now][i]]=1;
          len[graph[now][i]]=len[now]+1;
          q.push(graph[now][i]);
        }
   }
}
int main()
{
   cin>>m>>n>>pn;
   int res=999999;
   for(int i=1;i<=pn;i++)
     cin>>pos[i];
   for(int i=1;i<=m;i++)
   {
      int num;
      cin>>num;
      for(int j=1;j<=num;j++)
      {
         int t;
         cin>>t;
         for(int k=1;k<=pn;k++)
           if(t==pos[k])
           {
             target[k].push_back(i);
             break;
           }
         face[i].push_back(t);
      }
      face[i].push_back(face[i][0]);
      //build graph
      for(int k=1;k<i;k++)
      {
       
        for(int j=0;j<face[i].size()-1;j++)       
           for(int l=0;l<face[k].size()-1;l++)
              if((face[k][l]==face[i][j]&&face[k][l+1]==face[i][j+1])||(face[k][l]==face[i][j+1]&&face[k][l+1]==face[i][j]))
              {
                 graph[k].push_back(i);
                 graph[i].push_back(k);
                // cout<<"num "<<i<<": "<<k<<" and "<<i<<" are insert"<<endl;
                 goto loop;
              }
         loop:;
      }
      
   }
   /*
   for(int i=1;i<=m;i++)
   {
      cout<<i<<":  ";
      for(int j=0;j<graph[i].size();j++)
        cout<<graph[i][j]<<" ";
      cout<<endl;
   }
   cout<<endl<<endl;
   for(int i=1;i<=pn;i++)
   {
      cout<<i<<":   ";
      for(int j=0;j<target[i].size();j++)
        cout<<target[i][j]<<" ";
      cout<<endl;
   }
   system("pause");
   */
   for(int i=1;i<=m;i++)
   {
       bfs(i);
       int total=0;
       for(int j=1;j<=pn;j++)
       {
          int minnum=999999;
          for(int k=0;k<target[j].size();k++)
            minnum=min(minnum,len[target[j][k]]);
          total+=minnum;
       }
       res=min(res,total);
   }
   cout<<res<<endl;
  // system("pause");
   return 0;
   
}