求地图中的最小生成树。 多组输入。每个数据第一行为图中点的个数。紧接着n-1行，每行的第一个字母为图中的某一个点，（按照字典序升序），第二个数字表示这个点与比它字典序大的相连点的个数，然后后面紧接着为相连边的情况。 当地图中点的个数为0时，输入结束。 Input 9 A 2 B 12 I 25 B 3 C 10 H 40 I 8 C 2 D 18 G 55 D 1 E 44 E 2 F 60 G 38 F 0 G 1 H 35 H 1 I 35 3 A 2 B 10 C 40 B 1 C 20 0 Output 216 30 Sample Input 9 A 2 B 12 I 25 B 3 C 10 H 40 I 8 C 2 D 18 G 55 D 1 E 44 E 2 F 60 G 38 F 0 G 1 H 35 H 1 I 35 3 A 2 B 10 C 40 B 1 C 20 0 Sample Output 216 30 最小生成树prime写法，讲字符之间的路程转换成对应数组上的路程，用road存储两个点之间的最短路
#include<algorithm> #include<cstring> #include<vector> #include<map> #include<cmath> #include<cstdio> #include<queue> #include<iostream> typedef long long ll; const int mod = 150; const int maxn = 2500; const int inf = 0x3f3f3f3f; using namespace std; int n,m; int dis[maxn],road[maxn][maxn]; bool vis[maxn]; int prim() { int mi, v,ans=0; for(int i = 0; i < n; i++) { dis[i] = road[0][i]; vis[i] = false; } vis[0]=true; for(int i = 1; i < n; i++)//包括第一个点在内，一共要纳入n个点 { mi = inf; for(int j = 0; j < n; j++)//每次找出未纳入顶点集与已知顶点集构成的权值最小的一条边 { if(!vis[j] && mi > dis[j]) { v = j; mi = dis[j]; } } if(mi==inf) return -1; ans+=mi; vis[v] = true;//把该顶点纳入已知集合 for(int j = 0; j < n; j++)//更新与未纳入集合中的顶点的边的最小权值 { if(!vis[j] && dis[j] > road[v][j]) dis[j] = road[v][j]; } } return ans; } int main() { while(scanf("%d",&n)){//道路 城镇 if(n==0)break; for(int i=0;i<n;i++) for(int j=0;j<n;j++) road[i][j]=inf; for(int i=1;i<n;i++){ char u,v; int w,x; cin>>u>>w; while(w--){ cin>>v>>x; road[u-'A'][v-'A']=road[v-'A'][u-'A']=min(road[v-'A'][u-'A'],x); } } cout<<prim()<<endl; } return 0; }