[C++知识库]选取医院建立的位置

选取医院建立的位置

设a、b、c、d、e、f表示一个乡的6个村庄,弧上的权值表 示两村之间的距离。现要在这6个村庄中选择一个村庄建一所医院,问医院建在哪个村庄 才能使离医院最远的村庄到医院的距离最短?

输入格式:
输入的第一行为村庄个数
输入的其他是多个存在组成网络的邻接矩阵表示

输出格式:
输出医院建立的位置

输入样例:
在这里给出一组输入。例如：

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

输出样例:
在这里给出相应的输出。例如：

c

#include <stdio.h>
#include <stdlib.h>
#define MAX 65535
int a[10010][10010], vis[10010], rem[10010], n;///存放数据数组，标记访问数组，保存最小距离数组，记录点总的个数
void dijkstra(int start)
{
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=n;i++)
        rem[i]=MAX;
    rem[start]=0;
    for(int k=1;k<=n;k++)
    {
        int s=-1;
        for(int i=1;i<=n;i++)
            if(vis[i]==0&&(s==-1||rem[i]<rem[s])) ///s=-1 为第一次，rem[i]<rem[s] 找到所有距离中最小距离，因为要找多次，所以不用break，并且找到之后才标记访问
                s=i;
        vis[s]=1;
        for(int j=1;j<=n;j++)
            if(rem[s]+a[s][j]<=rem[j])
                rem[j]=rem[s]+a[s][j];
    }
}

int findLocation()
{
    int minnumber=1,minsum=MAX,tempsum=-MAX;
    for(int i=1;i<=n;i++) ///找到每次dijkstra中的最远 距离 ，并找到这些最远距离中的最小距离即可
    {
        tempsum=-MAX;
        dijkstra(i);
        for(int j=1;j<=n;j++)
            if(rem[j]>tempsum)
                tempsum=rem[j];
        if(tempsum<minsum)
        {
            minsum=tempsum;
            minnumber=i;
        }
    }
    return minnumber;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            scanf("%d",&a[i][j]);
    int location=findLocation();
    printf("%c",'a'+location-1);
    return 0;
}

202204021640六