任意两点间最短距离

每两点间遍历所有节点，更新最短距离

复杂度O(n^3)

 

板子

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              using namespace std;const int INF=0x3f3f3f3f;typedef pair
              
                pr;typedef long long ll;#define fi first#define se second#define me(x) memset(x, -1, sizeof(x))#define mem(x) memset(x, 0, sizeof(x))#define N 20000+5#define NIL -1int a[N][N];int n, m;void floyd(){ int i, j, k; for(k=1; k<=n; k++) for(i=1; i<=n; i++) { if(a[i][k]==INF) continue; for(j=1; j<=n; j++) { if(a[k][j]==INF) continue; a[i][j]=min(a[i][j], a[i][k]+a[k][j]); } }}int main(){ int i, j, k; int u, v, w; while(cin>>n>>m) { for(i=1; i<=n; i++) for(j=1; j<=n; j++) i==j ? a[i][j]=0 : a[i][j]=INF; for(i=0; i
               
                >u>>v>>w, a[u][v]=w;//双向 ,a[v][u]=w; floyd(); for(i=1; i<=n; i++) if(a[i][i]<0) break; if(i<=n) cout<<"negetive circle"<
                
                 1) cout<<' '; if(a[i][j]!=INF) cout<