题目传送门

题目大意

给出一张图，个点，条边，图上每条边的边权为
图上有个特殊点，两两之间可以连边，已经有边的也可以连边
连一条边，问图上到的最短路的最大值是多少

解题思路

从号点和号点各一遍，记正向距离为，反向距离为，则答案为
稍微变换一下，原式变为
按照升序排序
枚举每一个位置，最小值一定是,让这个值最大，维护的前缀最大值即可，赛场上这一部分一直想不出，我太菜了

AC代码

// #pragma GCC optimize(3,"Ofast","inline")
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <stack>
#include <vector>
#include <string>
#include <iostream>
#include <list>
#include <cstdlib>
#include <bitset>
#include <assert.h>
// #define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
// char buf[(1 << 21) + 1], * p1 = buf, * p2 = buf;
// #define int long long
#define lowbit(x) (x & (-x))
#define lson root << 1, l, mid
#define rson root << 1 | 1, mid + 1, r
#define pb push_back
typedef unsigned long long ull;
typedef long long ll;
typedef std::pair<int, int> pii;
#define bug puts("BUG")
const long long INF = 0x3f3f3f3f3f3f3f3fLL;
const int inf = 0x3f3f3f3f;
const int mod = 1000000007;
const double eps = 1e-6;
template <class T>
inline void read(T &x)
{
    int sign = 1;char c = getchar();x = 0;
    while (c > '9' || c < '0'){if (c == '-')sign = -1;c = getchar();}
    while (c >= '0' && c <= '9'){x = x * 10 + c - '0';c = getchar();}
    x *= sign;
}
#ifdef LOCAL
    FILE* _INPUT=freopen("input.txt", "r", stdin);
    // FILE* _OUTPUT=freopen("output.txt", "w", stdout);
#endif
using namespace std;
const int maxn = 2e5 + 10;
struct EDGE
{
    int next, to;
} edge[maxn << 1];
int head[maxn],tot;
int dis1[maxn], dis2[maxn];
bool sp[maxn];
int a[maxn];
inline void addedge(int u, int v)
{
    edge[tot] = {head[u], v};
    head[u] = tot++;
}
void bfs(int s, int t, int dis[])
{
    queue<int> q;
    q.push(s);
    dis[s] = 0;
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        for (int i = head[u]; ~i; i = edge[i].next)
        {
            int v = edge[i].to;
            if (dis[v] != inf)
                continue;
            dis[v] = dis[u] + 1;
            q.push(v);
        }
    }
}
pii aa[maxn];
bool cmp(const pii& a,const pii&b)
{
    return a.first - a.second < b.first - b.second;
}
int main()
{
    int n, m, k;
    int u, v;
    memset(head, -1, sizeof head);
    memset(dis1, 0x3f, sizeof dis1);
    memset(dis2, 0x3f, sizeof dis2);
    read(n), read(m), read(k);
    for (int i = 0; i < k; ++i)
    {
        read(a[i]);
        sp[a[i]] = 1;
    }
    for (int i = 0; i < m; ++i)
    {
        read(u), read(v);
        addedge(u, v);
        addedge(v, u);
    }
    bfs(1, n, dis1);
    bfs(n, 1, dis2);
    int tot = 0;
    for (int i = 0; i < k; ++i)
    {
        aa[tot++] = pii(dis1[a[i]], dis2[a[i]]);
    }
    sort(aa, aa + tot, cmp);
    int mx = -inf;
    int res = 0;
    for (int i = 0; i < tot; ++i)
    {
        res = max(res, aa[i].second + mx + 1);
        mx = max(mx, aa[i].first);
    }
    printf("%d\n", min(res, dis1[n]));
}