有一张个点的有向图，给定其邻接矩阵，若，则到之间没有连边，否则到有一条权值为的边。求该图任意两点间的最短距离。
区块链毕设网qklbishe.com为您提供问题的解答
有一张个点的有向图，给定其邻接矩阵
，若
，则
到
之间没有连边，否则
到
有一条权值为
的边。求该图任意两点间的最短距离。
#include<algorithm>
#include<iostream>
using namespace std;
const int N=510;
int n;
int d[N][N];
const int INF=0x3f3f3f3f;
void floyd()
{
for (int k = 1; k <= n; k ++ )
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= n; j ++ )
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
cin>>d[i][j];
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(d[i][j]==-1)
d[i][j]=INF;
floyd();
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(d[i][j]==INF)
d[i][j]=-1;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++)
cout<<d[i][j]<<" ";
cout<<endl;
}
return 0;
}
以上就是关于问题有一张个点的有向图，给定其邻接矩阵，若，则到之间没有连边，否则到有一条权值为的边。求该图任意两点间的最短距离。的答案
欢迎关注区块链毕设网-
专业区块链毕业设计成品源码，定制。
区块链NFT链游项目方科学家脚本开发培训
