首页 > 代码库 > HDU 1301 Jungle Roads
HDU 1301 Jungle Roads
最小生成树prim
1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 #include <algorithm> 5 #include <cmath> 6 using namespace std; 7 8 const int INF = 99999999 ; 9 const int maxn = 105 ;10 11 int map[maxn][maxn];12 int visit[maxn];13 int low[maxn];14 15 int main (){16 int n;17 while (~scanf ("%d",&n)&&n){18 for (int i=0;i<n;i++)19 for (int j=0;j<n;j++)20 map[i][j]=INF;21 for (int i=0;i<n-1;i++){22 char c[10];23 int a,b;24 scanf ("%s%d",c,&a);25 while (a--){26 scanf ("%s%d",c,&b);27 map[i][(int)(c[0]-‘A‘)]=map[(int)(c[0]-‘A‘)][i]=b;28 }//cout<<n<<" "<<i<<endl;29 }30 memset (visit,0,sizeof visit);31 int ans=0;32 int mi;33 int pos=1;34 visit[1]=1;35 for (int i=0;i<n;i++)36 low[i]=map[pos][i];37 for (int i=0;i<n-1;i++){38 mi=INF;39 for (int j=0;j<n;j++)40 if (!visit[j]&&low[j]<mi){41 mi=low[j];pos=j;42 }43 ans+=mi;visit[pos]=1;44 for (int j=0;j<n;j++)45 if (!visit[j])46 low[j]=min (low[j],map[pos][j]);47 }48 printf ("%d\n",ans);49 }50 return 0;51 }
HDU 1301 Jungle Roads
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。