哪位能人帮帮我,看看我哪错了
查看原帖
哪位能人帮帮我,看看我哪错了
767635
huyixuanpi楼主2022/11/29 20:27

看看我哪错了

#include<bits/stdc++.h>
using namespace std;
int a1[1001][1001],a2[1001][1001],c1[1001],c2[1001];
bool b1[1001],b2[1001];

int maxx = 1e9,n,m;
long long ans;
int main()
{
	cin>>n>>m;
	for(int i = 1;i<=n;i++)
	{
		for(int j = 1;j<=n;j++)
		{
			a1[i][j]=maxx;
			a2[i][j]=maxx;
		}
		a1[i][i]=0;
		a2[i][i]=0;
	}
	for(int i = 1;i<=m;i++)
	{
		int u,v,w;
		cin>>u>>v>>w;
		a1[u][v]=w;
		a2[v][u]=w;
	}
	memset(b1,false,sizeof(b1));
	
	memset(b2,false,sizeof(b2));
	for(int i = 1;i<=n;i++)
	{
		c1[i]=a1[1][i];
		c2[i]=a2[1][i];
	}
	for(int i = 2;i<=n;i++)
	{
		int min1 = maxx;
		int k1 = 0;
		for(int j = 1; j<=n; j++) {
			if((!b1[j])&&(c1[j]<min1)) {
				min1 = c1[j];
				k1 = j;
			}
		}
		if(k1==0)break;
		b1[k1]=true;
		for(int j = 1;j<=n;j++)
		{
			if(a1[k1][j]<maxx)
			{
		        c1[j]=min(c1[j],a1[k1][j]+c1[k1]);
			}
		}
	}
	
	
	
	for(int i = 1;i<=n;i++)
	{
		int min2 = maxx;
		int k2 = 0;
		for(int j = 1; j<=n; j++) {
			if((!b2[j])&&(c2[j]<min2)) {
				min2 = c2[j];
				k2 = j;
			}
		}
		if(k2==0)break;
		b2[k2]=true;
		for(int j = 1;j<=n;j++)
		{
			if(a2[k2][j]<maxx)
			{
		        c2[j]=min(c2[j],a2[k2][j]+c2[k2]);
			}
		}
	}
	for(int i = 2;i<=n;i++)
	{
		    ans+=c1[i];
		    ans+=c2[i];
	}
	cout<<ans<<endl;
	return 0;
}

2022/11/29 20:27
加载中...