All Pairs Shortest Path

链接:https://vjudge.net/problem/Aizu-GRL_1_C
思路:通过弗洛伊德算法,三重循环:d[k][j] = min(d[k][j],d[k][i] + d[i][j])更新出所有点的最短距离,若是存在封闭环的加权值为负数,则二维数组中d[i][i]中必然存在负值,所以只需单独判断是否存在负值,从而可以确定是否存在封闭环加权值为负数的情况.

代码:
#include<iostream>
#include<algorithm>
#include<vector>
#include<climits>
using namespace std;

static const int MAX = 100;
static const long long INFTY = (1LL<<32);

int n;
long long d[MAX][MAX];

void floyd(){
for(int i=0;i<n;i++)
for(int j=0;j<n;j++){
if(d[j][i]==INFTY)continue;
for(int k=0;k<n;k++){
if(d[i][k]==INFTY)continue;
d[j][k] = min(d[j][k],d[j][i]+d[i][k]);//弗洛伊德算法核心
}
}
}

int main(){
int times,a,b,now;

cin>>n>>times;
for(int i=0;i<n;i++)//初始化整个数组,将起点和终点相同的数组对应的值设为0
for(int j=0;j<n;j++){
if(i==j)d[i][j] = 0;
else d[i][j] = INFTY;
}

while(times--){
cin>>a>>b>>now;
d[a][b] = now;
}
floyd();

bool negative = false;

for(int i=0;i<n;i++)//判断是否存在加权值为负数的封闭环
if(d[i][i]<0)negative = true;
if(negative)cout<<"NEGATIVE CYCLE"<<endl;

else{
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(j)cout<<" ";
if(d[i][j]==INFTY)cout<<"INF";
else cout<<d[i][j];
}
cout<<endl;
}
}
return 0;
}