#include
#define?MaxInt?10000//最大數(shù)?
using?namespace?std;
const?int?MaxNumEdges=50;?
const?int?MaxNumVertices=10;?//最大頂點數(shù)?
class?Graph
{
????private:
????????int?vNum;//當(dāng)前頂點數(shù)
????????int?eNum;//當(dāng)前邊數(shù)
????????int?Vertex[MaxNumVertices];//頂點數(shù)組
????????int?Edge[MaxNumVertices][MaxNumVertices];//邊數(shù)組
????????bool?GetVertexPos（const?int?&vertexint?&i）;//給出頂點vertex在圖中的位置
????public:
????????Graph（const?int?sz=?MaxNumEdges）;//構(gòu)造函數(shù)
????????bool?FindVertex（const?int?&vertex）;
????????bool?InsertVertex（const?int?&?vertex）;//插入一個頂點vertex
????????bool?InsertEdge（const?int?v1const?int?v2const?int?weight）;//插入一條邊（v1v2）該邊上的權(quán)值為weight
????????void?Hospital（）;//醫(yī)院選址函數(shù)
};?
Graph::Graph（const?int?sz）:?vNum（0）?eNum（0）
//構(gòu)造函數(shù)
{?
????int?ne;
????int?nametailhead;
????int?weight;
????for（int?i=0;i????for（int?j=0;j????{
????????if（i==j）
????????????Edge[i][j]=0;//頂點到自身權(quán)值為0
????????else
????????????Edge[i][j]=10000;//鄰接矩陣初始化為最大值
????}
????printf（“請輸入頂點數(shù)注意本程序最多為10個!\n“）;
????scanf（“%d“&n）;
????printf（“請依次輸入頂點名稱:\n“）;
????for（int?i=0;i????{
????????scanf（“%d“&name）;
????????InsertVertex（name）;
????vNum++;
????}
????printf（“請輸入邊數(shù):\n“）;
????scanf（“%d“&e）;
????printf（“以下輸入邊信息:\n“）;
????for（int?i=0;i????{
????????printf（“請輸入第%d邊頭頂點:“i+1）;
????????scanf（“%d“&head）;
????????printf（“請輸入該邊尾頂點：“）;
????????scanf（“%d“&tail）;
????????printf（“請輸入該邊權(quán)值：“）;
????????scanf（“%d“&weight）;
????????if（!InsertEdge（headtailweight））
????????{
????????????printf（“不存在該邊，請重輸！\n“）;
????????????continue;
????????}
????}
}?
bool?Graph::FindVertex（const?int&?vertex）
//給出頂點vertex在圖中的位置
{
????for?（int?i?=?0;?i?????if?（vertex?==?Vertex[i]）
????????return?true;
????return?false;
}?
bool?Graph::?GetVertexPos（const?int?&vertexint?&i）
//給出頂點vertex在圖中的位置
{
????for?（i?=?0;?i?????if?（vertex?==?Vertex[i]）
????????return?true;
????return?false;
}?
bool?Graph::InsertVertex（const?int?&?vertex）
//插入一個頂點vertex
{
????if?（FindVertex（vertex））
????????return?false;
????Vertex[vNum]?=?vertex;
????return?true;
}?

bool?Graph::InsertEdge（const?int?v1const?int?v2const?int?weight）
//插入一條邊（v1v2）該邊上的權(quán)值為weight
{?
????int?k=0j=0;
????if（GetVertexPos（v1k）?&&?GetVertexPos（v2j））
????{
????????Edge[k][j]=weight;
????????eNum++;
????????Edge[j][k]=weight;
????????eNum++;
????????return?true;
????}
????else
????????return?false;
}?
void?Graph::Hospital（）?
//在以鄰接帶權(quán)矩陣表示的n個村莊中，求醫(yī)院建在何處，使離醫(yī)院最遠(yuǎn)的村莊到醫(yī)院的路徑最短。?
{
????int?kijs;
????for?（k=0;k????????for?（i=0;i????????????for?（j=0;j????????????????if?（Edge[i][k]+Edge[k][j]????????????????????Edge[i][j]=Edge[i][k]+Edge[k][j];
????int?m=MaxInt;?//設(shè)定m為機(jī)器內(nèi)最大整數(shù)。
????printf（“********************************************\n“）;
????//以下為求各村離醫(yī)院最近的醫(yī)院選址
????int?min=MaxInt?;?//設(shè)定機(jī)器最大數(shù)作村莊間距離之和的初值。
????k=0;?//k設(shè)醫(yī)院位置。
????for?（j=0;j