1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 using namespace std; 7  8 typedef long long ll; 9 const int maxn = 100 + 5;10 const int inf = 0x3f3f3f3f;11 int n, m, ans;12 int mp[maxn][maxn], dis[maxn][maxn], pos[maxn][maxn];13 vector
          
            path;　　　　//记录路径14 inline void getpath( int x, int y ){15 if( pos[x][y]==0 ) return;16 getpath( x, pos[x][y] );17 path.push_back(pos[x][y]);18 getpath( pos[x][y], y );19 }20 21 inline void floyd(){22 ans = inf;23 for( int k=1; k<=n; k++ ){24 for( int i=1; i
           
             dis[i][k]+dis[k][j] ){　　//此处要按dis[i][k]+dis[k][j]更新最短距离 而不是mp[i][k]+mp[k][j]37 dis[i][j] = dis[i][k]+dis[k][j];38 pos[i][j] = k;39 }40 }41 }42 43 int main(){44 scanf("%d%d", &n, &m);45 memset( mp, inf, sizeof(mp) );46 memset( pos, 0, sizeof(pos) );47 for( int i=0; i<=n; i++ ) mp[i][i] = 0;48 for( int i=0; i