View Code of Problem 1042

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<queue>
#include<algorithm>
#include<cmath>
#define oo 1000000007
#define MAXN 505
using namespace std;
int Dist[MAXN][MAXN],Graph[MAXN][MAXN];

int MC(int nVertex)
{
      int mincircle=oo,i,j,k,temp;
      for (i=0;i<nVertex;i++)
        for (j=0;j<nVertex;j++)
           Dist[i][j]=Graph[i][j];
      for(k=0;k<nVertex;++k)
      {
          //新增部分:
           for(i=0;i<k;++i)
               for(j=0;j<i;++j)
                  if (mincircle>Dist[i][j]+Graph[j][k]+Graph[k][i])
                     mincircle = Dist[i][j]+Graph[j][k]+Graph[k][i];
         //通常的 floyd 部分:
           for(i=0;i<nVertex;++i)
              for(j=0;j<i;++j)
              {
                     temp = Dist[i][k] + Dist[k][j];
                     if(temp < Dist[i][j])
                        Dist[i][j] = Dist[j][i] = temp;
              }
      }
      return mincircle;
}

int main()
{
       int C,cases,N,M,u,v,ans; 
       scanf("%d",&C);
       for (cases=1;cases<=C;cases++)
       {
                scanf("%d%d",&N,&M);
                for (u=0;u<N;u++)
                   for (v=0;v<N;v++)
                      Graph[u][v]=oo;
                while (M--)
                {
                        scanf("%d%d",&u,&v);
                        Graph[u][v]=Graph[v][u]=1;
                }
                ans=MC(N);
                printf("Case %d: ",cases);
                if (ans==oo) puts("impossible");
                        else printf("%d\n",ans);
       }
       return 0;
}