hdoj 1863 暢通工程 最小生成樹---prime算法

#include <iostream>  
#include <cstring>  
using namespace std; 
const int inf=0xffffff; 
int weight[105][105],n,m; 
int prime() 
{ 
    int sum=0; 
    int pre[105]; 
    int dis[105]; 
    bool visit[105]; 
    memset(visit,0,sizeof(visit)); 
    for(int i=1;i<=m;i++) 
    { 
        dis[i]=weight[1][i]; 
        pre[i]=1; 
    }    
     
    visit[1]=1; 
    for(int i=1;i<m;i++) 
    { 
        int minimum=inf; 
        int index=-1; 
        for(int j=1;j<=m;j++) 
        { 
            if(!visit[j] &&dis[j]<minimum){ 
                minimum=dis[j]; 
                index=j; 
            } 
        } 
        if(index==-1)return inf; 
        visit[index]=1; 
        sum+=weight[pre[index]][index]; 
        for(int j=1;j<=m;j++) 
        { 
            if(!visit[j]&& dis[j]>weight[index][j]) 
            { 
                dis[j]=weight[index][j]; 
                pre[j]=index; 
            } 
        } 
    } 
    return sum; 
}  
int main() 
{ 
    while(cin>>n>>m) 
    { 
        if(n==0)break; 
        for(int i=1;i<=m;i++) 
            for(int j=1;j<=m;j++) 
                weight[i][j]=inf; 
        for(int i=0;i<n;i++) 
        { 
            int x,y,z; 
            cin>>x>>y>>z; 
            weight[x][y]=z; 
            weight[y][x]=z; 
        } 
        int ans=prime(); 
        if(ans==inf){cout<<"?"<<endl;continue;} 
        cout<<ans<<endl; 
    } 
} 

#include <iostream>
#include <cstring>
using namespace std;
const int inf=0xffffff;
int weight[105][105],n,m;
int prime()
{
 int sum=0;
 int pre[105];
 int dis[105];
 bool visit[105];
 memset(visit,0,sizeof(visit));
 for(int i=1;i<=m;i++)
 {
  dis[i]=weight[1][i];
  pre[i]=1;
 } 
 
 visit[1]=1;
 for(int i=1;i<m;i++)
 {
  int minimum=inf;
  int index=-1;
  for(int j=1;j<=m;j++)
  {
   if(!visit[j] &&dis[j]<minimum){
    minimum=dis[j];
    index=j;
   }
  }
  if(index==-1)return inf;
  visit[index]=1;
  sum+=weight[pre[index]][index];
  for(int j=1;j<=m;j++)
  {
   if(!visit[j]&& dis[j]>weight[index][j])
   {
    dis[j]=weight[index][j];
    pre[j]=index;
   }
  }
 }
 return sum;
}
int main()
{
 while(cin>>n>>m)
 {
  if(n==0)break;
  for(int i=1;i<=m;i++)
   for(int j=1;j<=m;j++)
    weight[i][j]=inf;
  for(int i=0;i<n;i++)
  {
   int x,y,z;
   cin>>x>>y>>z;
   weight[x][y]=z;
   weight[y][x]=z;
  }
  int ans=prime();
  if(ans==inf){cout<<"?"<<endl;continue;}
  cout<<ans<<endl;
 }
}