-
题意
题目链接: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;
}
标签:结点,int,短路,long,Floyd,设置,include,dis
From: https://www.cnblogs.com/Shunn/p/17709980.html