题目链接:
http://acm.sdibt.edu.cn:8080/judge/contest/view.action?cid=400#problem/A
题目不难,就是用Dijkstra算法,代码如下:
#include <stdio.h>
int inf=100000;
int sum;
int dic[110];
int map[110][110];//图矩阵
int visit[110];//标记
void f(int n)
{  
  int i,j;
  sum=0;
  for(i=1;i<=n;i++)
  for(j=1;j<=n;j++)
 {  
  visit[i]=0;
  if(i==j)
       map[i][j]=0;
  else
  map[i][j]=inf;
  }
}
int prime(int n)//prim算法思想(Dijkstra)
{
   int min,rec,j,i,p=1;
   for(i=1;i<=n;i++)
       dic[i]=map[1][i];
   visit[1]=1;
   for(i=1;i<n;i++)
   {
    min=inf;
    for( j=1;j<=n;j++)
   {
    if(!visit[j]&&dic[j]<min)
   {
    min=dic[j];
    rec=j;
    }
    }
    if(min==inf)
    {
     p=0;
     break;
    }
    sum+=min;
    visit[rec]=1;
    for(j=1;j<=n;j++)
    {
    if(!visit[j]&&dic[j]>map[rec][j])
    {
    dic[j]=map[rec][j];
    }
    }
    }
   if(p!=0)
    return 1;
   return 0;
}
int main()
{
   int N,M,j,k,i,value,fer;
  while(scanf("%d%d",&N,&M),N)
  {
     f(M);
     for(i=1;i<=N;i++)
  { 
   scanf("%d%d%d",&j,&k,&value);
   if(value<map[j][k])
   map[j][k]=map[k][j]=value;
  }
   fer=prime(M);
   if(fer==1)
   printf("%d\n",sum);
   else
   printf("?\n");
  }
  return 0;
}

发表评论

电子邮件地址不会被公开。

Post Navigation