题目 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; }