#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;
}