//设a、b、c、d、e、f表示一个乡的6个村庄,弧上的权值表 示两村之间的距离。
// 现要在这6个村庄中选择一个村庄建一所医院,问医院建在哪个村庄 才能使离医院最远的村庄到医院的距离最短?
//解题思路：本体要求找到一个地点建医院，算出这个医院距离其它每个结点的最小距离，
// 然后找到每个出发点这些最小距离中最远的那个作比较。找到最远距离最小的那个输出。
//比如在a处建立医院，离医院最远的村庄到医院的距离记为DMa，则比较DMa,DMb,DMc,DMd,DMe,DMf这六个值哪个最小
typedef char VerTexType; //字符型顶点数据类型
typedef int ArcType; //边的权值类型为整型
//辅助数组，用来记录从顶点集到
struct
{
VerTexType adjvex;
ArcType lowcost;
} closedge[MVNum];
//图的邻接矩阵存储表示
typedef struct
{
VerTexType vexs[MVNum]; //顶点表
ArcType arcs[MVNum][MVNum];//邻接矩阵
int vexnum, arcnum; //节点数和边数
}AMGraph;
//找到出发点得位置
int LocateVex(AMGraph* G, VerTexType v)
{
for (int i = 0; i < G->vexnum; i++)
{
if (G->vexs[i] == v)
return i;
}
return -1;
}
//输入题中给的邻接矩阵
void Scanf(AMGraph* G, int n)
{
int i, j;
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
scanf("%d", &G->arcs[i][j]);
G->vexnum = n;
}
//测试用
void Print(AMGraph G)
{
int i, j;
for (i = 0; i < ; i++)
{
for (j = 0; j < ; j++)
printf("%d ", [i][j]);
printf("\n");
}
}
//从每个顶点出发，找最短路径
int Dijkstra(AMGraph G, int v0)
{
//S放是否选中过，D放起点距离其他点的距离，path放前驱结点，n是顶点个数
int S[6], D[6], Path[6];
int n = 6, i, w, v;
//初始化
for (v = 0; v < n; v++)
{
S[v] = false; //先把S都置为未选中过
D[v] = [v0][v]; //把顶点距离其他结点的距离输入
if (D[v] < MaxInt) Path[v] = v0; //如果v0到v有边，那就把v的前置结点写上
else Path[v] = -1; //如果没边，就把前置结点设置为-1代表没有
}
S[v0] = true; //起点设为选中过
D[v0] = 0; //起点到自己的距离为0
//开始找最小距离
int min;
for (i = 1; i < n; i++)
{
min = MaxInt;
for (w = 0; w < n; w++)
{
//没被选中 并且有边的 结点
if (!S[w] && D[w] < min)
{
//就记录下结点的位置
v = w;
//并把它的权值暂存为最小权值
min = D[w];
}
}
//最小边的结点改为被选中
S[v] = true;
//从新选中的结点开始寻找，
for (w = 0; w < n; w++)
{
//未被选中，并且从起始节点到目前能到达的结点的最小值
if (!S[w] && D[v] + [v][w] < D[w])
{
//总长度 = 之前长度的总和+到新结点的长度
D[w] = D[v] + [v][w];
//新结点的前置结点设置
Path[w] = v;
}
}
}
//找到每组最远的那个
int max = 0;
for (int s = 0; s < 6; s++)
{
if (max < D[s])
max = D[s];
}
return max;
}
int main()
{
//输入
AMGraph G;
int n;
scanf("%d", &n);
Scanf(&G, n);
int temp[6];
int min = 0;
//先把每组的最远距离搞出来
for (int i = 0; i < 6; i++)
{
temp[i] = Dijkstra(G, i);
printf("%d\n", temp[i]);
}
//找最远距离中最小的
for (int i = 0; i < 6; i++)
{
if (temp[min] > temp[i])
min = i;
}
//转换字符
char name = (char)min + 97;
printf("%c", name);
/*6
0 12 3 65535 9 10
12 0 65535 2 6 65535
3 65535 0 2 65535 6
65535 2 2 0 4 7
9 6 65535 4 0 4
10 65535 6 7 4 0
9 DMa
9 DMb
6 DMc
7 DMd
9 DMe
9 DMf
输出 c */
return 0;
}