求大佬解惑
查看原帖
求大佬解惑
1261787
jnkssss楼主2024/3/5 19:17

我用的Floyd,为什么我初始化为全正无穷能过,但是初始化为对角线0其他正无穷缺过不了,代码如下

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=1010;

int g[N][N];
int n,m;

void floyd()
{
	for(int k=1;k<=n;k++)
	    for(int i=1;i<=n;i++)
	        for(int j=1;j<=n;j++)
	            g[i][j]=min(g[i][j],g[i][k]+g[k][j]);
}

int main()
{
//	for(int i=1;i<=n;i++)
//	    for(int j=1;j<=n;j++)
//	        if(i==j) g[i][j]=0;
//	        else g[i][j]=0x3f3f3f3f;
    memset(g,0x3f,sizeof(g));
	cin>>n>>m;
	while(m--)
	{
		int a,b,c;
		cin>>a>>b>>c;
		g[a][b]=min(g[a][b],c);
	}
	floyd();
	int res=0;
	for(int i=2;i<=n;i++)
	{
		res+=g[1][i];
		res+=g[i][1];
	}
	cout<<res<<endl;
}
2024/3/5 19:17
加载中...