zoj 1406 Jungle Roads - 军军小站|张军博客

从A到F找到最短路即可，由于我不会用prim算法

只能用ku...算法，幸好这道题没有让输出路路径，

所以用ku...算法也行

我通常都是这样写的1.把边存起来2.快排3.并查集

呵呵，过了，还行吧，对了输入注意用scanf

中的%d前加一个空格

<span style="font-size: 18px;">#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>

typedef struct Tedge
{
    int from,to;
    int dist;
}edge;

edge dis[100];
int N;
int fa[30];

int find(int x)
{
   if(x == fa[x])
     return x;
   fa[x] = find(fa[x]);
   return(fa[x]);
}

int cmp(const void *a,const void *b)
{
   return (*(edge *)a).dist - (*(edge *)b).dist; 
}

int main()
{
    int n,sub,m,d,i,count,sum;
    char ch;
    while(scanf("%d",&n)==1,n)
    {
        N = 0;
        sub = n;
        sub -= 1; 
        while(sub--)
        {
           scanf(" %c",&ch);
           dis[N].from = ch - 'A' + 1;
           scanf("%d",&m);
           for(i=1;i<m;i++)
              dis[N+i].from = dis[N].from;
           while(m--)
           {
                scanf(" %c",&ch);
                scanf("%d",&d);
                dis[N].to = ch - 'A' + 1;
                dis[N].dist = d;
                N++;
           }
        }                                  //输入完成
        
        qsort(dis,N,sizeof(edge),cmp);   
        for(i=1;i<=n;i++)
          fa[i] = i;
        count =0;
        sum = 0;
        for(i=0;i<N;i++)
        {
            if(find(dis[i].from) != find(dis[i].to))
            {
                fa[find(dis[i].from)] = find(dis[i].to);
                sum += dis[i].dist;
                count++;
                if(count == (n-1))break;
            }
        }       
        
        printf("%d\n",sum);
        
    }
    return 0;
}
</span>

zoj 1406 Jungle Roads

更多文章、技术交流、商务合作、联系博主

微信扫码或搜索：z360901061

微信扫一扫加我为好友

QQ号联系： 360901061

您的支持是博主写作最大的动力，如果您喜欢我的文章，感觉我的文章对您有帮助，请用微信扫描下面二维码支持博主2元、5元、10元、20元等您想捐的金额吧，狠狠点击下面给点支持吧，站长非常感激您！手机微信长按不能支付解决办法：请将微信支付二维码保存到相册，切换到微信，然后点击微信右上角扫一扫功能，选择支付二维码完成支付。

【本文对您有帮助就好】元

2元

5元

10元

20元

自定义