首页 > 其他分享 >最短路之Floyd(医院设置)

最短路之Floyd(医院设置)

时间:2023-09-17 22:49:03浏览次数:36  
标签:结点 int 短路 long Floyd 设置 include dis

  • 题意

题目链接: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

相关文章

  • springboot中配置类型转换,设置开启矩阵变量
    2023-09-17packagecom.hh.springboot05.config;importcom.hh.springboot05.bean.Pet;importorg.springframework.context.annotation.Bean;importorg.springframework.context.annotation.Configuration;importorg.springframework.core.convert.converter.Conver......
  • 颜色和透明度设置
    透明度<el-color-pickerv-model="color"show-alpha></el-color-picker><script>exportdefault{data(){return{color:'rgba(19,206,102,0.8)'}}};</script>颜色<el-color-pick......
  • springboot中设置静态资源存放的位置
    2023-09-17加载图片的静态资源可以放在resources下面的四个文件夹中,命名必须为(1)“META-INF”下的“resources”或者(2)public或者(3)resources或者(4)static application.yml设置静态资源的访问路径设置静态资源存放的位置spring:mvc:static-path-pattern:/res/**......
  • FastAPI学习-21.response 参数-设置响应Cookies
    前言可以在 路径函数 中定义一个类型为 Response的参数,这样你就可以在这个临时响应对象中设置cookie了。response参数设置cookiesfromfastapiimportFastAPI,Responseapp=FastAPI()@app.post("/cookie-and-object/")defcreate_cookie(response:Response):......
  • FastAPI学习-20.response 参数-设置响应头部
    前言你可以在你的_路径操作函数_中声明一个Response类型的参数。设置响应头部你可以在这个_临时_响应对象中设置头部fromfastapiimportFastAPI,Responseapp=FastAPI()@app.get("/headers-and-object/")defget_headers(response:Response):response.headers......
  • Jquery设置select控件指定text的值为选中项
    北环路天河路清华园路徐寨路朝凤路园田路varstreet=‘清华园路’;(‘#streetidoption:contains(’+street+‘)’).each(function(){if((this).text()==street){$(this).attr(‘selected’,true);}});......
  • jquery设置图片可手动拖拽
    JQuery是一款流行的JavaScript框架,可以轻松实现网页交互效果。而其中一种常见效果是图片手动拖拽。以下是设置图片手动拖拽的JQuery代码。$(document).ready(function(){varisDragging=false;varmousePos={x:0,y:0};varelemPos={x:0,y:0};var$elem=$......
  • html怎么设置按钮返回顶部
    在HTML中,我们可以通过一些代码和CSS样式来创建一个这样的按钮。<buttononclick="topFunction()"id="myBtn">返回顶部</button><style>#myBtn{display:none;position:fixed;bottom:20px;right:30px;z-index:99;border:none;outline:none;ba......
  • IDEA 反撤销快捷键设置
    Ctrl+Y在IDEA设置#在Windows中Ctrl+Z#撤销Ctrl+Y#撤销你的撤销【redo】而在IDEA中,Ctrl+Y是删除当前行,在settings中进行修改:搜索deleteline再搜索redo......
  • rider 设置多个启动项目
    要设置多个启动项目,您可以按照以下步骤操作:1.打开Rider并导航到"Run"菜单。2.选择"EditConfigurations"以打开配置窗口。3.在左侧的配置窗口中,单击"+"图标以添加新的启动配置。4.选择您要添加的项目类型(例如,ASP.NETCore、ConsoleApplication等)。5.配置您的启动......