第46行的cout,我用来检查,删掉以后答案就不对,但不删的话答案是正确的!
#include<bits/stdc++.h>
using namespace std;
int const N=5003,M=200003;
int g[N][N],dis[N],n,m,su;
bool st[N];
int find(){
int an,in=0x3f3f3f3f;
for(int i=1;i<=n;i++){
if(dis[i]<in && !st[i]){
in=dis[i];
an=i;
}
}
st[an]++;
return an;
}
/*-------法二
int t=-1;
for(int j=1;j<=n;j++){
if(!st[j] && (t==-1 || dis[j]<dis[t]))
t=j;
}
st[t]=1;
*/
int main(){
cin>>n>>m;
memset(g,0x3f,sizeof(g));
memset(dis,0x3f,sizeof(dis));
for(int i=1;i<=m;i++){
int x,y,z;
cin>>x>>y>>z;
if(x==y) continue;
g[x][y]=min(g[x][y],z);//防止重边。
g[y][x]=min(g[y][x],z);
}
dis[1]=0;//编号1的点距离为0.
for(int i=1;i<=n;i++){
int x=find();
for(int j=1;j<=n;j++) dis[j]=min(dis[j],min(g[j][x],g[x][j]));//枚举其他边。
cout<<x<<' '<<dis[x]<<endl;
if(i!=1 && dis[x]==0x3f3f3f3f){
cout<<"orz";//无法到达,
return 0;
}
su+=dis[x];
}
cout<<su;
return 0;
}
/*
5 6
1 2 3
2 3 4
3 1 4
4 5 6
5 4 6
1 3 5
*/
那一行代码加上,就输出orz,不加就输出15.