/*N(N>10)個居民區(qū)之間需要鋪設(shè)煤氣管道。假設(shè)任意兩個居民區(qū)之間都可以
鋪設(shè)煤氣管道，但代價不同。事先將任意兩個居民區(qū)之間鋪設(shè)煤氣管道的代
價存入磁盤文件中。設(shè)計一個最佳方案使得這N個居民區(qū)之間鋪設(shè)煤氣管道所需
代價最少，并希望以圖形方式在屏幕上輸出結(jié)果。*/




#include<iostream.h>
#include<stdlib.h>
#include<iomanip.h>
#include<stdio.h>
#include<fstream.h>

typedef char ElemType;
const int QueueMaxSize=30;

#include"queue.h"
const int MaxVertexNum=100;
const int MaxEdgeNum=100;
const int MaxValue=1000;
typedef char VertexType;
typedef VertexType vexlist[MaxVertexNum];
typedef int adjmatrix[MaxVertexNum][MaxVertexNum];
bool visited[MaxVertexNum];

struct edge
{
	int fromvex;
	int endvex;
	int weight;
};
typedef edge edgeset[MaxEdgeNum];

void Create(vexlist GV,adjmatrix GA,int n,int e)
{
	int i,j;
	/*cout<<"輸入"<<n<<"個頂點"<<endl;
	for(i=0;i<n;i++)
		cin>>GV[i];*/
	for(i=0;i<n;i++)
		for(j=0;j<n;j++)
		{
			if(i==j)
				GA[i][j]=0;
			else
				GA[i][j]=MaxValue;
		}
	/*	cout<<"輸入"<<e<<"條邊"<<endl;
		for(k=0;k<e;k++)
		{
			cin>>i>>j>>w;
			GA[i][j]=GA[j][i]=w;
		}*/
	/*	for(i=0;i<=n;i++)
		{
			for(j=0;j<=n;j++)
			{
				if(i==j)*/
	int v,m;
	FILE *fp;
	fp=fopen("data.txt","r");
	fscanf(fp,"%d %d",&v,&m);
	//cout<<v<<' '<<e<<endl;
	for(int x=1;x<=m;x++)
	{
		int i,j,k;
		fscanf(fp,"%d %d %d",&i,&j,&k);
		GA[i][j]=GA[j][i]=k;
	}
					
}

void Prim(adjmatrix GA,edgeset CT,int n)
{
	int min,t,m,w;
	for(int i=0;i<n-1;i++)
	{
		CT[i].fromvex=0;
		CT[i].endvex=i+1;
		CT[i].weight=GA[0][i+1];
	}
	for(int k=1;k<n;k++)
	{
		min=MaxValue;
		m=k-1;
		for(int j=k-1;j<n-1;j++)
			if(CT[j].weight<min)
			{
				min=CT[j].weight;
				m=j;
			}
			edge temp=CT[k-1];
			CT[k-1]=CT[m];
			CT[m]=temp;
			j=CT[k-1].endvex;
			for(i=k;i<n-1;i++)
			{
				t=CT[i].endvex;
				w=GA[j][t];
				if(w<CT[i].weight)
				{
					CT[i].weight=w;
					CT[i].fromvex=j;
				}
			}
	}
}


void main()
{
	int d;
	for(d=1;d<=20;d++)
		cout<<' ';
	cout<<"管道鋪設(shè)施工的最佳方案選擇"<<endl;//<<endl;
	//cout<<"數(shù)科院"；
    //int d;
	//for(d=1;d<=6;d++)
		//cout<<' ';
	cout<<"數(shù)科院"<<' '<<"06010824"<<' '<<"李方力"<<endl;//<<endl;
	cout<<"請注意:本程序管道起點必須為0!"<<endl;//<<endl;
	vexlist GV;
	adjmatrix GA;
	edgeset CT;
	int v,e;
	FILE *fp;
	fp=fopen("data.txt","r");
	fscanf(fp,"%d %d",&v,&e);
	cout<<"點數(shù):"<<v<<setw(6)<<' '<<"邊數(shù):"<<e<<endl;//<<endl;
	Create(GV,GA,v,e);
//	cout<<"輸出各邊的起點，終點以及權(quán)值:"<<endl;
	for(int x=1;x<=e;x++)
	{
		int i,j,k;
		fscanf(fp,"%d %d %d",&i,&j,&k);
		if(i!=0&&x==1)
		{
			cout<<"請看清本程序要求!"<<endl;
			exit(1);
		}
        if(x==1)
			cout<<"輸出:"<<' '<<"起點"<<setw(6)<<"終點"<<setw(6)<<"權(quán)值:"<<endl;
	//	cout<<i<<' '<<' '<<' '<<j<<' '<<' '<<' '<<k<<endl;
		cout<<' '<<' '<<' '<<' '<<' '<<' '<<' '<<i<<setw(6)<<j<<setw(6)<<k<<endl;
	}
	//cout<<endl;
	Prim(GA,CT,v);
	cout<<"輸出最短路徑:"<<endl;
	int sum=0;
	FILE *f;
	f=fopen("data1.txt","w");
	fprintf(f,"輸出最短路徑存檔:\n");
	for(int m=0;m<v-1;m++)
	{
	//	FILE *f;
	//	f=fopen("data1.txt","w+t");
		if(m==5)
			cout<<endl;
        fprintf(f,"%d->%d\n",CT[m].fromvex,CT[m].endvex);
		cout<<CT[m].fromvex<<"->"<<CT[m].endvex<<setw(4);
		
		sum=sum+GA[CT[m].fromvex][CT[m].endvex];
	}
	cout<<endl;
    fprintf(f,"輸出最短路徑代價存檔:%d\n",sum);
	fclose(f);
	cout<<"最佳方案所需代價:"<<sum<<endl;
}