main.cpp

实现岛上建立公路的最短路径算法

/*********************************************
*********主函数实现
*********************************************/
#include "island.h"

int main()
{
	int n,p,q,a,b,c;
	int i,j;
	struct MGraph G;
	n = p = q = i = j = 0;
	scanf("%d %d %d",&n,&p,&q);
	GraphInit(G,n);
/************************************
***以下为输入部分
************************************/
while (i<p)
	{
		scanf("%d %d",&a,&b);	//已经存在通路不用修路的景点
		*(*(G.arcs+a-1)+b-1) = 0;
		*(*(G.arcs+b-1)+a-1) = 0;
		i++;
	}
	i = 0;
	while (i<q)					//需要修路的景点信息
	{
		scanf("%d %d %d",&a,&b,&c);
		*(*(G.arcs+a-1)+b-1) = c;
		*(*(G.arcs+b-1)+a-1) = c;
		i++;
	}
/*	i = j = 0;					//自己编的测试邻接矩阵的函数，已注释
	while (i<n)
	{
		while (j<n)
		{
			printf("%d\t",G.arcs[i][j]);
			if (j==n-1)
			{
				printf("\n");
			}
			j++;
		}
		j = 0;
		i++;
	}*/
	printf("%d\n",Mini_SpanTree_PRIM(G,n));//输出调用Prim算法求出的修路总代价

	return 0;
}