先写一下这周发生的事情吧，这周我们是劳动周，我被分配到了站岗排车子的保卫组，虽然倒是没有什么活干， 但是由于是在户外，天气太冷了有没有，真的是手都要冻掉了，但是我可以偷懒来实验室打代码（嘿嘿这倒是还不错），但是还是有查岗的，所以还是小心翼翼的，这周注定是艰苦的一周，这周天好像还有比赛要打，加油！昨天和前天就做了一道1900 的图论题，现在想出来倒是没啥了，但是没有想出来之前是真的难啊有没有，真的是折磨，痛并快乐着。
少点压力，不要看的太重。
本来就一无所有，所以变成什么样子都无所谓吧。
题目地址
首先我们明白题意是我们需要在特殊点之间加边以至于加边所构成的新图中，最短路最长。
思路：我们假设如果加了一条边使得新图的最短路比原图要短，那么我们新图中的那个最短路一定是会经过该条边，所以我们这时候会出现一个思路是：首先利用 b f s bfs bfs求出来以1号点，n号点为起点的最短路， 然后枚举每两个特殊点 i , j i, j i,j，在他们之间建边，这里由于我们的边是双向边，不知道从哪个方向走比较短，所以我们还需要判断一下我们需要从哪个方向走，取最短的那个方向。我们在枚举的时候只要发现在某两点之间加边所构成的经过改边的最短路大于原图最短路我们就可以说明我们的答案就可以是原图中的最短路，但是我们发现我们k 的数据范围是 2 e 5 2e5 2e5，所以不加优化肯定是不行的，我自己的优化虽然也是过掉了，但是过程跟粑粑一样，这里直接说下榜单大佬的优化，首先我们可以将一个点所构成的距离两个距离放到 pair 中去，然后我们可以根据这个 d 1. f i r s t + d 2. s e c o n d < d 1. s e c o n d + d 2. f i r s t d1.first + d2.second < d1.second + d2.first d1.first+d2.second<d1.second+d2.first 然后移项 d 1. f i r s t − d 1. s e c o n d < d 2. f i r s t − d 2. s e c o n d d1.first - d1.second < d2.first - d2.second d1.first−d1.second<d2.first−d2.second 这样我们所构成的这样二元组 d i . f i r s t + d j . s e c o n d ( i < j ) di.first + dj.second (i <j) di.first+dj.second(i<j)一定是合法的，所以我们只需要求出这样的二元组 最大值就可以了！ 代码：
#include <iostream> #include <cstring> #include <vector> #include <algorithm> using namespace std; const int N = 4e5 + 10, M = 2 * N, INF = 0x3f3f3f3f; int h[N], e[M], ne[M], w[M], idx; int q[N * 2]; int dist[N], undist[N]; int n, m, k; int f[N]; bool st[N], vis[N]; void add (int a, int b, int c) { e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++; } void spfa (int start, int dist[]) { for (int i = 0; i <= n; i ++) dist[i] = INF; memset (vis, 0, sizeof vis); int hh = 0, tt = 0; dist[start] = 0; q[tt ++] = start; while (hh != tt) { int t = q[hh ++]; if (hh == N) hh = 0; vis[t]= false; for (int i = h[t]; i != -1; i = ne[i]) { int j = e[i]; if (dist[j] > dist[t] + w[i]) { dist[j] = dist[t] + w[i]; if (!vis[j])q[tt ++] = j, vis[j] = true; if (tt == N) tt = 0; } } } } int main() { memset (h, -1, sizeof h); scanf ("%d%d%d", &n, &m, &k); vector <int> arr; for (int i = 1; i <= k; i ++) { int a; scanf ("%d", &a); arr.push_back (a); } for (int i = 1; i <= m; i ++) { int a, b; scanf ("%d%d", &a, &b); add (a, b, 1), add (b, a, 1); } spfa (1, dist); spfa (n, undist);// lost but never end. l'm loser.\ pair <int, int> a[N]; for (int i = 0; i < k; i ++) a[i] = {dist[arr[i]], undist[arr[i]]}; sort (a, a + k, [&] (pair<int, int> a, pair <int, int> b) { return a.first - a.second < b.first - b.second; }); int res = 0, Max = a[0].first; for (int i = 1; i < k; i ++) { res = max (res, Max + a[i].second + 1); Max = max (Max, a[i].first); } if (res <= dist[n]) printf ("%d", res); else printf ("%d", dist[n]); return 0; }