洛谷 P2935 [USACO09JAN]最好的地方Best Spot

2024-01-29 20:18

本文主要是介绍洛谷 P2935 [USACO09JAN]最好的地方Best Spot,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目传送门
.
.
.
.
.

分析

水题一道
先用Flody算出各点之间的最短路
求和点到F_i的距离
再比较谁更短即可
.
.
.
.
.

程序:
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int p,f,c,fi[1000],g[510][510];
int main()
{scanf("%d%d%d",&p,&f,&c);for (int i=1;i<=f;i++) scanf("%d",&fi[i]);memset(g,0x3f,sizeof(g));for (int i=1;i<=c;i++){int u,v,w;scanf("%d%d%d",&u,&v,&w);g[u][v]=g[v][u]=w;}for (int i=1;i<=p;i++)g[i][i]=0;for (int k=1;k<=p;k++)for (int i=1;i<=p;i++)for (int j=1;j<=p;j++)if (g[i][k]+g[k][j]<g[i][j]) g[i][j]=g[i][k]+g[k][j];int ans=0,bz=2147483647;for (int i=1;i<=p;i++){int sum=0;for (int j=1;j<=f;j++)sum+=g[i][fi[j]];if (sum<bz) {bz=sum;ans=i;}}printf("%d",ans);
}

这篇关于洛谷 P2935 [USACO09JAN]最好的地方Best Spot的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/658060

相关文章

最好用的WPF加载动画功能

《最好用的WPF加载动画功能》当开发应用程序时,提供良好的用户体验(UX)是至关重要的,加载动画作为一种有效的沟通工具,它不仅能告知用户系统正在工作,还能够通过视觉上的吸引力来增强整体用户体验,本文给... 目录前言需求分析高级用法综合案例总结最后前言当开发应用程序时,提供良好的用户体验(UX)是至关重要

无线路由器哪个品牌好用信号强? 口碑最好的三个路由器大比拼

《无线路由器哪个品牌好用信号强?口碑最好的三个路由器大比拼》不同品牌在信号覆盖、稳定性和易用性等方面各有特色,如何在众多选择中找到最适合自己的那款无线路由器呢?今天推荐三款路由器让你的网速起飞... 今天我们来聊聊那些让网速飞起来的路由器。在这个信息爆炸的时代,一个好路由器简直就是家庭网编程络的心脏。无论你

Java 文件读写最好是用buffer对于大文件可以加快速度

参考例子: FileReader fileReader = new FileReader(filename);BufferedReader bufferedReader = new BufferedReader(fileReader);List<String> lines = new ArrayList<String>();String line = null;while ((line =

高精度计算(代码加解析,洛谷p1601,p1303)除法待更新

目录 高精度加法 高精度减法 高精度乘法 高精度加法 我们知道在c++语言中任何数据类型都有一定的表示范围。当两个被加数很大时,正常加法不能得到精确解。在小学,我们做加法都采用竖式方法。那么我们也只需要按照加法进位的方式就能得到最终解。 8 5 6+ 2 5 5-------1 1 1 1 加法进位: c[i] = a[i] + b[i];if(c[i] >=

洛谷 凸多边形划分

T282062 凸多边形的划分 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 先整一个半成品,高精度过两天复习一下补上 #include <iostream>#include <algorithm>#include <set>#include <cstring>#include <string>#include <vector>#include <map>

笔试强训,[NOIP2002普及组]过河卒牛客.游游的水果大礼包牛客.买卖股票的最好时机(二)二叉树非递归前序遍历

目录 [NOIP2002普及组]过河卒 牛客.游游的水果大礼包 牛客.买卖股票的最好时机(二) 二叉树非递归前序遍历 [NOIP2002普及组]过河卒 题里面给的提示很有用,那个马的关系,后面就注意,dp需要作为long的类型。 import java.util.Scanner;// 注意类名必须为 Main, 不要有任何 package xxx 信息publ

能量项链,洛谷

解释:  环形dp问题还是考虑将环拉直,可以参考我上一篇文章:环形石子合并 [2 3 5 10 2] 3 5 10 将环拉直,[]内是一个有效的区间,可以模拟吸收珠子的过程,         如[2 3 5] <=>(2,3)(3,5)    2是头,3是中间,5是尾 len >= 3:因为最后[2 10 2]是最小的可以合并的有效区间 len <= n + 1因为[2 3

二分猜数易错的地方

今天做简单的二分猜数问题,while循环总是跳不出去,搞了好久才弄好了。。。好几次都这样,总结一下吧 while(left <= right){int mid = (left+right)/2;if(ok(mid)) left = mid+1,ans = mid;//记录结果,要不然跳不出循环,视题目而定,ans也可以写在下面else right = mid-1;}

最好的超声波清洗机是哪款牌子?高颜值的超声波清洗机

超声波清洗机凭借其出色的洁净能力与简便的操作方式,正逐渐成为广受欢迎的清洁优选。它以深度而不伤材质的清洗效果著称,不过市面上品牌琳琅满目,型号多样,价格波动大,给消费者挑选造成了不小的挑战。作为一名眼镜爱好者,我对超声波清洗机颇有研究,并乐意在此为朋友们推荐几款品质卓越的机型,希望能对你选购超声波清洗机有所帮助! 超声波清洗机选购攻略 技巧1:优选专业实力强悍的品牌 在选择超声波清洗机时,偏

洛谷P5490扫描线

0是最小的数字,将一个线段看成一个区间,对于一个矩形,从下扫到上,入边为1,而出边为-1,意思是将这个区间上的所有点加1(区间修改).把线段表示为Line[i],其中记录了l,r,h,tag,左右端点,高度,入边还是出边(1或-1) 那么每次区间修改后不为0的区间它的值可能是1,2,3或者是其它数字,这不好统计,可以将它转化一下,0是不是表示没有被覆盖过的地方,我们只要统计0的个数然后用总长减去