poj 1161 最短路构图

题目链接：http://poj.org/problem?id=1161

#include <cstdio>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <queue>
#include <vector>

#define maxn 400
#define INF  0x3f3f3f
#define min(a,b) (a>b?b:a)
using namespace std;

int first[maxn][maxn]; 
int d[maxn][maxn];
vector<int> G[maxn];
int N,M,L;
int mem[35];

void floyd(){
    for(int k=1;k<=M;k++)
       for(int i=1;i<=M;i++){
          for(int j=1;j<=M;j++){
              d[i][j] = min(d[i][j],d[i][k]+d[k][j]);
          }
       }      
}
int main()
{
    scanf("%d%d%d",&M,&N,&L);    
    for(int i=1;i<=L;i++){
        scanf("%d",&mem[i]);
    }
    memset(first,0,sizeof(first));
    memset(d,0x3f,sizeof(d)); 
    for(int i=1;i<=M;i++){
        int k,a,b,c;
        scanf("%d%d",&k,&a);
        G[a].push_back(i);
        k--;   b = a;
        while(k--){
            scanf("%d",&c);
            G[c].push_back(i);
            if(!first[b][c])
                first[b][c] = first[c][b] = i;
            else{
                d[first[b][c]][i] = d[i][first[c][b]] = 1;  //复制粘贴的代码太可怕了 
             }
            b = c;
        }
        if(!first[a][b])
            first[a][b] = first[b][a] = i;
        else{
            d[first[a][b]][i] = d[i][first[a][b]] = 1;
        }
    }
       
       for(int i=1;i<=M;i++) d[i][i] = 0;
       floyd();
   
       int ans = INF;
    for(int i=1;i<=M;i++){
        int sum = 0;
        for(int j=1;j<=L;j++){
            int u = mem[j];  
            int mincross = INF;
            for(int k=0;k<G[u].size();k++){
                int v = G[u][k];
                mincross = min(mincross,d[v][i]);
            }
            sum += mincross;    
        }
        ans = min(ans,sum);    
    }
    printf("%d
",ans);
}
 

反正是WA的很伤心啊！