医院设置

链接

又是一道和树路径有关的题目,上一次是<小红的奇数奶油球>,我用的dfs

这次用bfs(n这次也超级小的,本来还担心超时)

和那题很相似,唯一的难点在于距离如何计算

分析一下就会发现,设节点j到节点i的距离为dis[i],显然dis[j]=0

那么,只需让dis[i]=dis[k]+1即可(k为i的上一个节点)

#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;
#define ll long long
const int MAX=105;
int n;
vector<int>node[MAX];//每个节点都分别通往什么节点
vector<ll>people(MAX);//每个节点的人数
ll dis[MAX];
bool visited[MAX];
ll f(int hospital) {
//每次开始都记得重置一下
    memset(visited, 0, sizeof(visited));
    memset(dis, -1, sizeof(dis));
    dis[hospital] = 0;
    ll sum = 0;
    queue<int>q;
    q.push(hospital);
    while (!q.empty()) {
        int cur = q.front();
        visited[cur] = 1;
        q.pop();
        //cout << "dis:" << dis[cur] << '\n';
        for (int num : node[cur]) {
            if (visited[num]) continue;
            dis[num] = dis[num] == -1 ? dis[cur] + 1 : dis[num];//路径计算就在这里
            sum += people[num] * dis[num];
            q.push(num);
           //cout << num << " ";
        }
       // cout << '\n';
    
    }
    return sum;
}
int main() {
    cin >> n;
    for (int i = 1;i <= n;i++) {
        int w, u, v;
        cin >> w >> u >> v;
        people[i] = w;
        if (u != 0) {
            node[i].push_back(u);
            node[u].push_back(i);
        }
        if (v != 0) {
            node[i].push_back(v);
            node[v].push_back(i);
        }
    }
    ll result = 1e9;
    for (int i = 1;i <= n;i++) {
        //cout << i << ":" << '\n';
        result = min(f(i), result);
        //cout << f(i) << '\n';
    }
    cout << result;
}

时间复杂度:O(n²)

空间复杂度:O(n)