问题 A: 【图】医院设置（Floyd算法）

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了问题 A: 【图】医院设置（Floyd算法），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含999字，纯文字阅读大概需要2分钟。

内容图文

题目

题解：
1.数据量小，可以直接使用邻接矩阵存图，读题可知相邻节点的距离为1，而人数是节点的权值

2.先初始化邻接矩阵dis[i][j]=INF，dis[i][i]=0,输入时dis[i][l]=1,dis[l][i]=1…

3.直接使用Floyd算法，更新节点间的最短距离，及连通性

4.遍历所有节点，求出建立在哪个节点的距离和最小

上代码：

#include <iostream>

using namespace std;
const int INF=1000000;
int a[105][105];
int dis[105];
void init(){for(int i=1;i<=100;i++)for(int j=1;j<=100;j++) a[i][j]=INF,a[i][i]=0;}
void Floyed(int n)
{
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                a[i][j]=min(a[i][j],a[i][k]+a[k][j]);

}
int main()
{
    init();///初始化
    int n;cin>>n;
    for(int i=1;i<=n;i++)
    {
        int a1,b,d;
        cin>>dis[i]>>a1>>b;
        ///输入图节点的数据
        if(a1!=0)a[i][a1]=1,a[a1][i]=1;
        if(b!=0) a[i][b]=1 ,a[b][i]=1;
    }
    int ans=INF*100+1;
    Floyed(n);///更新节点间最小距离
    for(int i=1;i<=n;i++)
    {
        int minn=0;
        for(int j=1;j<=n;j++)
        {
            if(a[i][j]!=INF) minn+=a[i][j]*dis[j];///求出建立在节点i上的最小距离
        }
        if(ans>minn) ans=minn;///更新最小距离和
    }
    cout << ans << endl;
    return 0;
}

内容总结

以上是互联网集市为您收集整理的问题 A: 【图】医院设置（Floyd算法）全部内容，希望文章能够帮你解决问题 A: 【图】医院设置（Floyd算法）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---