48 lines
1.2 KiB
C++
48 lines
1.2 KiB
C++
#include <bits/stdc++.h>
|
||
|
||
using namespace std;
|
||
|
||
const int N = 210;
|
||
const int INF = 0x3f3f3f3f;
|
||
int minn = INF;
|
||
int n, m, k;
|
||
int d[N][N]; //邻接矩阵存储
|
||
int p[N];
|
||
|
||
// 算法结束后，d[a][b]表示a到b的最短距离,k->i->j
|
||
void floyd() {
|
||
for (int k = 1; k <= n; k++)
|
||
for (int i = 1; i <= n; i++)
|
||
for (int j = 1; j <= n; j++)
|
||
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
|
||
}
|
||
|
||
|
||
int main() {
|
||
cin >> n;
|
||
//floyd初始化
|
||
for (int i = 1; i <= n; i++)
|
||
for (int j = 1; j <= n; j++)
|
||
if (i == j) d[i][j] = 0;
|
||
else d[i][j] = INF;
|
||
|
||
//读入数据
|
||
for (int i = 1; i <= n; i++) {
|
||
int a, b;
|
||
cin >> p[i] >> a >> b;
|
||
if (a) d[a][i] = d[i][a] = 1;
|
||
if (b) d[b][i] = d[i][b] = 1;
|
||
}
|
||
//弗洛依德算法
|
||
floyd();
|
||
|
||
//模拟
|
||
for (int i = 1; i <= n; i++) {//模拟1-n的每一个结点，尝试将医院放在这里
|
||
int s = 0; //看看取得的”所有居民所走的路程之和“是多少，取最小值
|
||
for (int j = 1; j <= n; j++) s += d[i][j] * p[j];
|
||
//取最小值
|
||
minn = min(minn, s);
|
||
}
|
||
cout << minn << endl;
|
||
return 0;
|
||
} |