57 lines
1.8 KiB
C++
57 lines
1.8 KiB
C++
#include <bits/stdc++.h>
|
||
|
||
using namespace std;
|
||
const int N = 210;
|
||
bool d[N][N]; //这里n小我就直接邻接矩阵了，如果用邻接表还能快点
|
||
bool st[N]; //是不是使用过了,这个是必须要有了，否则不就死循环了吗
|
||
int p[N]; //权值数组
|
||
int n; //n个医院
|
||
int ans = 0x3f3f3f3f; //答案
|
||
|
||
struct Node {
|
||
int sq_sum; //几号结点
|
||
int step;//到这个结点走了多少步了
|
||
};
|
||
|
||
//bfs找当前点x为医院设置点时的总距离
|
||
int bfs(int x) {
|
||
//每次计算前需要清空一下使用过的标识数组
|
||
memset(st, 0, sizeof(st));
|
||
|
||
//队列
|
||
queue<Node> q;
|
||
st[x] = true; //使用过了
|
||
q.push({x, 0});//放入队列
|
||
|
||
int sum = 0;//本次运算的权值和
|
||
|
||
while (!q.empty()) {
|
||
Node node = q.front();
|
||
q.pop();
|
||
for (int i = 1; i <= n; i++)
|
||
//如果两个结点之间是联通的，并且没有走过
|
||
if (d[node.num][i] && !st[i]) {
|
||
//准备继续探索
|
||
Node next = {i, node.step + 1};
|
||
sum += p[i] * next.step; //权值在增加
|
||
st[i] = true; //标识使用过了
|
||
q.push(next); //放入队列
|
||
}
|
||
}
|
||
return sum;
|
||
}
|
||
|
||
int main() {
|
||
//读入数据到邻接矩阵
|
||
cin >> n;
|
||
for (int i = 1; i <= n; i++) {
|
||
int l, r;
|
||
cin >> p[i] >> l >> r;
|
||
if (l) d[i][l] = d[l][i] = true;//为0表示无链接,双向建图
|
||
if (r) d[i][r] = d[r][i] = true;//为0表示无链接,双向建图
|
||
}
|
||
//遍历每个结点作为医院部署地
|
||
for (int i = 1; i <= n; i++) ans = min(ans, bfs(i));
|
||
cout << ans << endl;
|
||
return 0;
|
||
} |