第一种代码:
#include<bits/stdc++.h>
using namespace std;
#define N 101
int a[N],f[N][N],n,l,r,i,j,k,s,minn=1000000;
int main()
{
scanf("%d",&n);
memset(f,1000000,sizeof(f));
for(i=1;i<=n;++i)
{
f[i][i]=0;
scanf("%d%d%d",&a[i],&l,&r);
if(l>0)
{
f[i][l]=1;
f[l][i]=1;
}
if(r>0)
{
f[i][r]=1;
f[r][i]=1;
}
}
for(k=1;k<=n;++k)
for(i=1;i<=n;++i)
if(i!=k)
for(j=1;j<=n;++j)
if(i!=j&&k!=j&&f[i][k]+f[k][j]<f[i][j])
f[i][j]=f[i][k]+f[k][j];
for(i=1;i<=n;++i)
{
s=0;
for(j=1;j<=n;++j)
s+=f[i][j]*a[j];
if(s<minn)
minn=s;
}
printf("%d",minn);
return 0;
}
20分
第二种代码:把memset换成了手写
#include<bits/stdc++.h>
using namespace std;
#define N 101
int a[N],f[N][N],n,l,r,i,j,k,s,minn=1000000;
int main()
{
scanf("%d",&n);
for(i=1;i<=n;++i)
for(j=1;j<=n;++j)
f[i][j]=1000000;
for(i=1;i<=n;++i)
{
f[i][i]=0;
scanf("%d%d%d",&a[i],&l,&r);
if(l>0)
{
f[i][l]=1;
f[l][i]=1;
}
if(r>0)
{
f[i][r]=1;
f[r][i]=1;
}
}
for(k=1;k<=n;++k)
for(i=1;i<=n;++i)
if(i!=k)
for(j=1;j<=n;++j)
if(i!=j&&k!=j&&f[i][k]+f[k][j]<f[i][j])
f[i][j]=f[i][k]+f[k][j];
for(i=1;i<=n;++i)
{
s=0;
for(j=1;j<=n;++j)
s+=f[i][j]*a[j];
if(s<minn)
minn=s;
}
printf("%d",minn);
return 0;
}
AC......