1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 #include
           
             8 #include
            
              9 using namespace std;10 #define N 11111 int f[N][N],lj[N][N];12 int n,m;13 vector
             
              q;14 void init()15 {16 memset(f,0,sizeof(0));17 memset(lj,-1,sizeof(lj));18 }19 void floyd()20 {21 for(int k=1;k<=n;k++)22 {23 for(int i=1;i<=n;i++)24 {25 for(int j=1;j<=n;j++)26 {27 if(f[i][j]>f[i][k]+f[k][j])28 {29 f[i][j]=f[i][k]+f[k][j];30 lj[i][j]=k;31 }32 }33 }34 }35 }36 37 void dfs(int u,int v)38 {39 if(lj[u][v]==-1)return ;40 dfs(u,lj[u][v]);41 q.push_back(lj[u][v]);42 dfs(lj[u][v],v);43 }44 void print()45 {46 for(int i=1;i<=n;i++)47 {48 for(int j=1;j<=n;j++)49 {50 if(i==j)continue;51 printf("%d->%d = %d ",i,j,f[i][j]);52 q.clear();53 q.push_back(i);54 dfs(i,j);55 q.push_back(j);56 for(int k=0;k