本文最后更新于:2020年4月11日 下午

  • 寻找从城镇或道路上的家到最近的购物中心的最大距离是有问题的。

  • 我们需要分别去分析。

首先,找到每个城镇到购物中心的最短距离。○是镇,写在里面的数字是镇号。带有橙色数字的小镇是带有购物中心的小镇。蓝色数字是道路的长度。

8Ra96U.png

这个时候,我们可以使用Dijkstra算法。

Dijkstra的算法是一种计算最短路径的算法。
说一种算法是什么,
反复说,“最短距离来确定从短顶点的最短距离”
是一种算法。(在这种情况下,顶部是城镇。)通过
“决定”,您可以消除浪费。
我认为仅凭这一点很难理解,所以让我们具体解释一下。

在初始状态下,“确定了最短距离的顶点”是顶点2和4,并且距离是0。

对于其他顶点,尚未确定最短距离,因此请设置足够大的数字$INF$(= 100000001)。 现在,最短的距离是顶点3的最短距离,而距顶点4的距离是1。 现在,最短的距离是顶点1的最短距离,到顶点4的距离是2。 看起来像这样。 在示例中,比例尺有点小,但是如果您这样做,则可以安全地使用较大的比例尺。 我认为使用优先级队列来实现是很常见的。

8RaVt1.png

8RaZfx.png

8Ramp6.png

现在已经确定了从每个城镇到购物中心的最短距离。
令$v[i]$为从$i$镇到购物中心的最短距离。

道路

道路分为以下两种模式。

  1. 他是某个城镇到购物中心的最短路径。

  2. 他与购物中心无关。

①的示例是上图中的4-3和3-1。(Ij表示连接城镇i和城镇j的道路。)

②的示例为上图中的1-2、2-3和2-4。
在①的情况下,离道路上的购物中心最远的点是最高点。

在②的情况下,例如在1-2的情况下,
如下绘制从道路上的一个点到购物中心的距离。 图的相交点是该道路上距购物中心最远的点。

用等式表示距离变成了$(v[1]+v[2]+$路径长度$)/ 2$

由于存在“四舍五入”的条件,也就是

$(v [1] + v [2] $+道路长度$+ 1)/ 2$

因此,该公式可以应用于①的情况。

代码如下:

$Code$


#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
#define rep(i,n) for(int i = 0; i < n; i++)
#define rrep(i,n) for(int i = 1; i <= n; i++)
#define pb push_back
#define p1 first
#define p2 second
using namespace std;
typedef pair<int,int> P;

const int INF = 100000001;

struct e{int t, d;};
struct road{int f, t, d;};

vector<e> p[3001];
vector<road> ro;
int v[3001];

int main(){
	int n, m, k, a, b, l, s, ans = 0;
	P x;
	scanf("%d%d%d", &n, &m, &k);
	
	priority_queue<P, vector<P>, greater<P> > q;
	
	rrep(i,n) v[i] = INF;
	rep(i,m){
		scanf("%d%d%d", &a, &b, &l);
		p[a].pb((e){b,l}); p[b].pb((e){a,l});
		ro.pb((road){a,b,l});
	}
	rep(i,k){
		scanf("%d", &s);
		q.push(P(0,s));
	}
	
	while (!q.empty()) {
		x = q.top(); q.pop();
		if(v[x.p2] == INF){
			v[x.p2] = x.p1;
			rep(i,p[x.p2].size()) q.push(P(x.p1 + p[x.p2][i].d, p[x.p2][i].t));
		}
	}
	
	rep(i,ro.size()) ans = max(ans, (v[ro[i].f] + v[ro[i].t] + ro[i].d + 1) / 2);
	
	printf("%d\n",ans);
	
	return 0;
}

结构描述

e:记录出某个城镇的出路。对于目的地,t是“到”,对于路径长度,d是“距离”。
道路:这只是一条“道路”。f是“起点”起点,与上面相同。

变量说明

p:记录离开某个城镇的道路。
ro:记录道路信息。
v:某个城镇与购物中心之间的最短距离。
n,m,k,a,b,l,s:输入。
ans:答案。
x:用于临时撤消q的内容的变量。


本文在 CC BY-NC-ND 4.0( https://creativecommons.org/licenses/by-nc-nd/4.0/deed.zh )协议 的前提下,禁止超过文章30%字数的摘录(对于不超过文章30%字数的摘录,要求在醒目位置注明原文作者与原文链接),同时,在未经作者本人手写签名许可的情况下,禁止任何形式的全文转载,禁止发布任何基于本文的再创作。

题解 AT3862 【異世界数式】 上一篇
题解 AT1121 【通勤電車と気分】 下一篇
本博客采用 xCss 的 Valine 评论系统,搭配了 Valine-Admin,垃圾评论将会被过滤。所以在评论的时候,请注意您的语言。如果您的评论被过滤但并非垃圾评论,请发邮件到 luosiweimail@gmail.com 进行申诉。