526互联

最短路之Floyd（医院设置）

发布时间 2023-09-17 22:30:08作者: shunn

  • 题意

题目链接：https://www.luogu.com.cn/problem/P1364

给一个二叉树，每个结点有一个值，这个值代表这个结点（即城市）有多少人，然后需要在这些结点中选出一个结点作为医院，问选哪个结点得到的距离和最小。距离和为人数乘以路径长度。

  • 思路

用最短路，就是先求出每两个点之间的最短路，然后遍历一遍，找到最小值。
用的是Floyd算法，Floyd算法代码很简洁，就是先设一个数组dist[i][j]，代表i ，j 之间的最短路径，然后就是一个三重循环，所以时间复杂度为 o(n^3) ，很大，所以该算法只适用于数据很小的时候。还要注意dist数组一开始要先初始化。

讲一下核心算法

for (int k = 1; k <= n; k ++){
        for (int i = 1; i <= n; i ++){
            for (int j = 1; j <= n; j ++){
                dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
            }
        }
 }

就是像动态规划
三重循环，可以理解为找了一个中间点 k ，然后求 i 到 j ，那么肯定可以在 i 到 j 之间找到一个点（包含 i ，j）k，那么就可以把 i 到 j 的距离转化成 i 到 k 加上 k 到 j。然后不断更新，找到最小值。

  • 代码

#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<vector>
#include<set>
#include<queue>
#include<math.h>
#include<stack>
#include<map>
#include<list>
#include<unordered_set>
#include<unordered_map>
#define endl '\n';
//#define int long long;
using namespace std;
typedef long long ll; 
const int Maxn = 2e8+10;
int n, m, k;
int dis[105][105], w[105];

void sovle(){
    cin >> n;

    for (int i = 1; i <= n; i ++){
        for (int j = 1; j <= n; j ++){
            dis[i][j] = Maxn; // 初始化dis数组
        }
    }

    for (int i = 1; i <= n; i ++){
        dis[i][i] = 0;
        int u, v;
        cin >> w[i] >> u >> v;
        if (u > 0){
            dis[u][i] = dis[i][u] = 1;
        }
        if (v > 0) {
            dis[v][i] = dis[i][v] = 1;
        }
    }

    for (int k = 1; k <= n; k ++){
        for (int i = 1; i <= n; i ++){
            for (int j = 1; j <= n; j ++){
                dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]); //核心代码
            }
        }
    }

    ll mini = Maxn;
    for (int i = 1; i <= n; i ++){
        ll sum = 0;
        for (int j = 1; j <= n; j ++){
            sum += dis[i][j] * w[j];
        }
        mini = min(mini, sum);
    }

    cout << mini << endl;
}

int main()
{	
    int t = 1; 
    //scanf("%d", &t);
    
    while (t --){
        sovle();
    }

    return 0;
}