Restoring Road Network（弗洛伊德算法的使用）

Restoring Road Network（中石油6610）

弗洛伊德算法的使用。

代码：
 

#include <iostream>
using namespace std;

const int N=305;
int arr[N][N];
const int inf=1e9+10;

int main()
{
    int n;
    while(cin>>n)
    {
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
            {
                cin>>arr[i][j];    
            }    
        for(int i=1;i<=n;i++)
            arr[i][i]=inf;
        long long sum=0;
        
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                for(int temp=1;temp<=n;temp++)
                {
                    int select=(arr[i][temp]==inf||arr[temp][j]==inf)?inf:(arr[i][temp]+arr[temp][j]);
                    if(select<arr[i][j]&&arr[i][j]!=inf)        
                    {
                        cout<<"-1"<<endl;
                        goto x; 
                    }
                    //else if()       
                }
    for(int j=1;j<=n;j++)            
        for(int i=j+1;i<=n;i++)         
            {
                int flag=0;
                for(int temp=1;temp<=n;temp++)        
                {
                    int select=(arr[i][temp]==inf||arr[temp][j]==inf)?inf:(arr[i][temp]+arr[temp][j]);
                    if(select==arr[i][j])            
                        flag=1;
                }
                if(flag==0)
                    sum=sum+arr[i][j];                  
            } 
        cout<<sum<<endl;    
        x:;
    }    
    return 0;               
}
 

 

总结

以上是生活随笔为你收集整理的Restoring Road Network（弗洛伊德算法的使用）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。