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（弗洛伊德算法的使用）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。