现在的位置: 首页 > 综合 > 正文

hdu 1301 prime Jungle Roads

2013年08月12日 ⁄ 综合 ⁄ 共 981字 ⁄ 字号 评论关闭

题目  http://acm.hdu.edu.cn/showproblem.php?pid=1301

我在这个题目中犯了二个错误哦,很纠结这个题目有不难  下次一定注意   第一个错误是输入有错误  搞的我一直错了,

第二个是   A 到B跟B到A点距离是相同的。

下面看具体ac代码

#include<iostream>
#include<cstring>
#include<cstdio>
#include<iomanip>
using namespace std;
#define inf 999999

int map[101][101];  ///图
bool mark[101];
int dis[101];
int n;

void prime()
{
    memset(mark,false,sizeof(mark)); ///标记
    memset(dis,0,sizeof(dis));   ///距离
    int sum,k,i,j,min;

    sum=0;
    for(i=1;i<=n;i++)
    {
        dis[i]=map[1][i];
    }
    dis[1]=0;
    mark[1]=true;

    for(i=2;i<=n;i++)
    {
        min=inf;
        k=0;
        for(j=1;j<=n;j++)   ///找出最短的距离
        {
            if(!mark[j]&&min>dis[j])
            {
                min=dis[j];
                k=j;
            }
        }
        sum+=min;

        mark[k]=true; ///标记

        for(j=1;j<=n;j++)  ///更新
        {
            if(map[k][j]&&!mark[j]&&dis[j]>map[k][j])
            {
                dis[j]=map[k][j];
            }
        }
    }
   cout<<sum<<endl;
}

int main()
{
    int i,j,k,t,m1,m2;
    char a,b;
    while(scanf("%d",&n)!=EOF,n)
    {
        memset(map,inf,sizeof(map)); ///初始化

       for(i=1;i<n;i++)
       {
           cin>>a>>k;  ///k代表这个点跟几个点相连哦
           for(j=0;j<k;j++)
           {
               cin>>b>>t;
               m1=a-'A'+1;  ///注意我是从1开始的所以要加1 。。
               m2=b-'A'+1;
              /// cout<<"m1  "<<m1<<"  m2  "<<m2<<endl;
               map[m2][m1]=map[m1][m2]=t; ///这里一定要注意哦。。。
           }
       }
       prime();
    }
    return 0;
}

 

抱歉!评论已关闭.