#include<fstream>

using namespace std;

ifstream fin("zlxd.in");

ofstream fout("zlxd.out");

int f[1001][1001],v[1001];bool visited[1001];

int main()

{

int n,m,x,y,a,i,j;

fin>>n>>m;

for(i=1;i<=n;i++)

for(j=1;j<=n;j++)

f[i][j]=0x7fffffff;

for(i=1;i<=m;i++)

{

fin>>x>>y>>a;

f[x][y]=f[y][x]=a;

}

memset(visited,0,sizeof(visited));

int dos=1;visited[dos]=1;

for(i=1;i<=n;i++)

if(i!=dos) v[i]=f[i][dos];

int total=0,min;

for(i=1;i<n;i++)

{

dos=1;

min=0x7fffffff;

for(j=1;j<=n;j++)

if(visited[j]==0&&min>v[j]) {dos=j;min=v[j];}

if(dos==1) break;

total=total+min;

visited[dos]=1;

for(j=2;j<=n;j++)

if(visited[j]==0&&v[j]>f[j][dos])

v[j]=f[j][dos];

}

fout<<total;

system("pause");

}

为什么只过两个点？

状态: Unaccepted

测评机： Xeost[5]

得分： 20分

提交日期： 2011-11-6 13:56:00

有效耗时： 235毫秒

RQNOJ近期在线比赛列表

RQNOJ十一月月赛 时间:2011-11-6 19:00:00 [报名]

测试结果1: 通过本测试点|有效耗时172ms

测试结果2: 选手程序运行超过时限

测试结果3: 测试结果错误.错误结果为:56342

正确结果应为:139949

测试结果4: 测试结果错误.错误结果为:56342

正确结果应为:83199

测试结果5: 测试结果错误.错误结果为:56342

正确结果应为:165204

测试结果6: 选手程序运行超过时限

测试结果7: 测试结果错误.错误结果为:56342

正确结果应为:37870

测试结果8: 测试结果错误.错误结果为:56342

正确结果应为:159982

测试结果9: 测试结果错误.错误结果为:56342

正确结果应为:50493

测试结果10: 通过本测试点|有效耗时63ms

#include<cstdio>

#include<climits>

#include<iostream>

#include<cstring>

#include<cstdlib>

int n,m,a[1005][1005],d[1005],ans=0,mi=INT_MAX,f,k,x,y,z;

bool v[1005];

int read()

{

char c; int f=1;

while((c=getchar())<'0' || c>'9') if(c=='-') f=-1;

int x=c-'0';

while((c=getchar())>='0' && c<='9') x=(x<<3)+(x<<1)+c-'0';

return x*f;

}

void prim()

{

int i,j;

memset(v,false,sizeof(v));

for(i=1;i<=n;i++) d[i]=INT_MAX;

f=1;

d[1]=0;

for(i=1;i<=n;i++)

{

mi=INT_MAX;

for(j=1;j<=n;j++)

{

if(v[j]==false && d[j]<mi)

{

mi=d[j];

k=j;

}

}

v[k]=true;

ans+=mi;

for(j=1;j<=n;j++)

{

if(a[k][j]<d[j]) d[j]=a[k][j];

}

}

printf("%d",ans);

}

int main()

{

int i,j;

n=read();

m=read();

for(i=1;i<=n;i++)

{

for(j=1;j<=n;j++)

{

a[i][j]=INT_MAX;

}

}

for(i=1;i<=m;i++)

{

x=read(),y=read(),z=read();

//printf("%d\n",z);

a[x][y]=z;

a[y][x]=z;

}

prim();

return 0;

}