#include "stdio.h"
#define MAX 1000
//单位为百亿元
typedef struct
{

char vexs[10][8]; 
//存放城市名称，最多存放10个城市
int edges [10][10];//存储每条高铁的修建费用
int n,e;
//分别代表图的顶点数和边数
}Mgraph;
struct
{

//存储该边上的权值
int lowcost;
//存储该边依附在集合U中的顶点下标
int vex;
//辅助数组
}CloseEdge[10];
//创建高铁线路网
void CreateMGraph(Mgraph *G)
{

int i,j,k,w;

printf("请输入城市个数和修建的高铁条数:");

scanf("%d,%d", &G->n,&G->e);

for(i=0;i<G->n;i++)
{

printf("请输入第%d个城市名称:",i+1);
scanf("%s", G->vexs[i]);
}
printf("各城市序号为:n");
for(i=0;i<G->n;i++)
printf ("%s:%d\t",G->vexs[i],i+1);
printf("\n");
for(i=0;j<G->n;j++)//邻接矩阵初始化
{

for(i=0;j<G->n;j++) G->edges[i][j]=MAX; 
//假设修建费用为最大
G->edges[i][i]=0;
//到本城市的费用为0
}
for (k=0;k<G->e;k++)
//建立邻接矩阵
{
printf("请输入修建第%d条高铁两个城市序号及修建费用:",k+1);
scanf("%d,%d,%d",&i,&j,&w);
//输入边的一对顶点序号
G->edges[i-1][j-1]=w;
G->edges[j-1][i-1]=w;
}
}
//求最小距离值,返回下标
int Minvalue(int n)
{

int j,k;
for(j=0;j<n;j++)
if(CloseEdge[j].lowcost>0)
{
k=j;break;
}
for(j=0;j<n;j++)
if (CloseEdge[j].lowcost>0&&CloseEdge[j].lowcost<CloseEdge [k].lowcost)
k=j;
return k;
}
//用普里姆算法构造最小生成树
void Prim(Mgraph *G,int u)
{

//pp用于记录最小生成树中边的下标
int cc=0, pp[20];
int k=0,i,j,s1;
for(i=0;i<G->n;i++)
{

CloseEdge [i].vex=u;
CloseEdge[i].lowcost=G->edges[u][i];
}
CloseEdge[u].lowcost=0;
for(i=1;i<G->n;i++)
//最小生成树的G->n-1条
{
k=Minvalue(G->n);
s1=CloseEdge[k].vex;
//边(s1,k)是一条权值最小的边
CloseEdge[k].lowcost=0;//将顶点k加入集合U中
pp[cc++]=s1;
pp[cc++]=k;
for(j=0;j<G->n;j++)
if (G->edges [k][j]<CloseEdge[j].lowcost)
{
CloseEdge[j].lowcost-G->edges[k][j];
CloseEdge[j].vex=k;
}
}
printf("高铁修建最经济万案为:\n");

for(i=0;i<2*(G->n-1);i=i+2)

printf("应修建高铁:%s<=>%s,费用:%d\n",G->vexs[pp[i]],G->vexs[pp[i+1]],G->edges[pp[i]][pp[i+1]]);
}

main()
{

Mgraph G;
CreateMGraph(&G);
Prim(&G,0);
}