Cf #179 (Div. 1) B. Greg and Graph 活用三重floyd-白红宇

Cf #179 (Div. 1) B. Greg and Graph 活用三重floyd

阅读量：4113 次

发布时间：2019-05-25

本文共 987 字，大约阅读时间需要 3 分钟。

题意：给了一个 n(1≤n≤500) 个点的有向完全图，以及邻接矩阵，现在每次删掉一个点，并问删掉这个点之后，总共删 n 次。没删掉一个点，都要求出剩余图中，所有顶点之间的最短路的和是多少，并输出

#include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
            
              #include 
              #include 
              
                #include 
               
                 using namespace std; typedef long long ll; typedef unsigned long long Ull; #define MM(a,b) memset(a,b,sizeof(a)); const double eps = 1e-10; const int inf = 0x3f3f3f3f; const double pi=acos(-1); const int mod=100000000; ll max(ll a,ll b) {return a>b?a:b;}; int min(int a,int b) {return a
                
                 =1;k--)//每次加入一个节点，就以改点更新整个图，将暴力的n^4降到n^3 { int cur=ope[k]; use[cur]=1; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) dp[i][j]=min(dp[i][j],dp[i][cur]+dp[cur][j]);//更新整个图 for(int i=1;i<=n;i++) if(use[i])//如果已经加入该节点 for(int j=1;j<=n;j++) if(use[j]) ans[k]+=dp[i][j]; } for(int i=1;i<=n;i++) printf("%lld ",ans[i]); printf("\n"); } return 0; }

分析：活用floyd的三重循环，降低复杂度，注意ans是求和，所以会爆int

转载地址：http://lxgsi.baihongyu.com/

你可能感兴趣的文章