最短路径如何才能尽可能长？转载本文请联系派珀蛋巢公众号。记录一道题解，题目来自Acwing.com第11期周赛。https://www.acwing.com/activity/content/59/我没有参加。如果我被要求这样做，我做不到。难度是难的，不是一道Template题，知识点bfs之类的简单，但是考的是分析能力。我的笔记：https://github.com/PiperLiu/ACMOI_Journey/tree/master/notesmaximizetheshortestpath[1]givenAnundirectedconnectedgraphwithvertexsandedges。图中的所有点均已编号。图中没有多条边和自环。将图中的点指定为特殊点。现在，您必须选择两个特殊点并在这两个点之间添加一条边。两个选定点之间允许存在预先存在的边。我们希望在加边操作完成后，点到点的最短距离尽可能大。输出这个最短距离的最大可能值。请注意，图中所有边（包括新添加的边）的长度为。输入格式的第一行包含三个整数。第二行包含整数，表示特殊点的个数，成对不同。接下来的几行，每行包含两个整数，表示点与点之间有一条边。输出格式是一个整数，表示最短距离的最大可能值。数据范围内的前六个测试点满足.所有测试点满足,,,,。输入样本1:5531351223343524输出样本1:3输入样本2:5422412233445输出样本2:3本次比赛为中等难度题目，重在分析。分析的第一步是讨论情况。题目要求必须在特殊点中选择两个点，并在两个点之间添加一条新的边。优化目标是在添加边后最大化从1到n的最短路径。从1到n的最短路径只能有以下三种情况（如上图所示）：不经过a到b这条线经过a->b，则距离为x[a]+1+y[b]经过b->a，距离为x[b]+1+y[a]解释：x[a]是1到a的距离，y[b]是n到b的距离如果我们在a和b之间加一条边，那么最终的最短路径距离就是下面三个中的最小值：原来的最短路径长度x[a]+1+y[b]x[b]+1+y[a]我们没有办法改变“原来的最短路径长度”，所以只能寄希望于min(x[a]+1+y[b],x[b]+1+y[a])的值为尽可能大。因此，我们需要考虑所有特殊点的成对组合，然后找到最大的min(x[a]+1+y[b],x[b]+1+y[a])ab组合。要找到成对组合，我们不能直接找到min(x[a]+1+y[b],x[b]+1+y[a])的最大值，所以我们必须逐步-步推导：x[a]+1+y[b]<=x[b]+1+y[a]即x[a]-y[a]<=x[b]-y[b]即当x[a]-y[a]<=x[b]-y[b],min(x[a]+1+y[b],x[b]+1+y[a])是x[a]+1+y[b]即我们求a,b满足x[a]-y[a]<=x[b]-y[b]（这个约束也可以让我们遍历所有的组合ofa,b),使得x[a]+1+y[b]找到最大的成对组合如上，我们将特殊点按照x[i]-y[i]的升序排序；我们让b作为第一层循环：即先确定b（如果是i）和a在图中的位置，选择起点到i的最大值即可，因为我们的目标是红色图中的直线有最大值，即y[b]+1+x[a]。#include
