题目链接

题意

有一个 $n$ 个点 $m$ 条边的无向图，每个点有点权 $h_i$，每条边有边权 $w_i$，让你找出一条从 $1$ 到 $n$ 的路径，在最小化路径长度的情况下最小化路径上最大点权和最小点权的差。

$n \le 5 \times 10^3,~m \le 2 \times 10^4,~h_i \le 9 \times 10^9,~w_i > 0,~\sum w_i \le 1 \times 10^{18}$

分析

先从 $1$ 开始跑一遍单源最短路求出所有点到 $1$ 的距离。

然后我们维护一个双指针，第一个指针枚举路径最小值的点权，第二个指针维护能够满足条件的最小的路径最大值的点权。判断当前的最小值和最大值的限制是否合法的方式也非常简单，从 $1$ 开始向 $n$ BFS，途中只经过能使得路径最短的边（通过判断路径两端的点到 $1$ 的距离之差是否为当前边边权即可）和满足限制的点（即点权在最小值和最大值之间），检验是否能 BFS 到 $n$ 即可。答案即为双指针过程中出现过的最小的两个点之间的差。

代码

这里提供来自出题人的 std。

#include <cstdio>
#include <algorithm>
#include <queue>
#include <memory.h>
using namespace std;
const long long inf = 0x3f3f3f3f3f3fLL;
struct line
{
    int from;
    int to;
    long long v;
    bool flag;
    int next;
};
struct line que[500005];
struct node
{
    int id;
    long long dis;
    bool operator <(const node &b)const
    {
        return dis > b.dis;
    }
};
struct point
{
    int id;
    long long height;
    bool operator <(const point &b)const
    {
        return height < b.height;
    }
};
struct point height[100005];
int cnt, headers[100005], n, m;
long long dis[100005];
bool vis[100005], ava[100005], book[100005];
void add(int from,int to,long long v)
{
    cnt++;
    que[cnt].from = from;
    que[cnt].to = to;
    que[cnt].v = v;
    que[cnt].next = headers[from];
    headers[from] = cnt;
}
void dijkstra(int s)
{
    priority_queue<node> q;
    q.push((node){s, 0});
    memset(dis, 0x3f3f, sizeof(dis));
    dis[s] = 0;
    while(!q.empty())
    {
        node tp = q.top();
        q.pop();
        if(vis[tp.id])
            continue;
        for (int i = headers[tp.id]; i;i=que[i].next)
            if(dis[que[i].to]>dis[tp.id]+que[i].v)
            {
                dis[que[i].to] = dis[tp.id] + que[i].v;
                q.push((node){que[i].to, dis[que[i].to]});
            }
    }
}
bool bfs(int s,int t)
{
    if(!ava[s] || !ava[t])
        return 0;
    queue<int> q;
    q.push(s);
    memset(book, 0, sizeof(book));
    book[s] = 1;
    while(!q.empty())
    {
        int tp = q.front();
        q.pop();
        for (int i = headers[tp]; i;i=que[i].next)
            if(que[i].flag && ava[que[i].to] && !book[que[i].to])
            {
                book[que[i].to] = 1;
                q.push(que[i].to);
            }
    }
    return book[t];
}
int main()
{
    //freopen("upsanddowns30.in","r",stdin);
    //freopen("upsanddowns30.out", "w", stdout);
    int u, v;
    long long w;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
    {
        scanf("%lld", &height[i].height);
        height[i].id = i;
    }
    sort(height + 1, height + n + 1);
    for (int i = 1; i <= m; i++)
    {
        scanf("%d%d%lld", &u, &v, &w);
        add(u, v, w);
        add(v, u, w);
    }
    dijkstra(1);
    for (int i = 1; i <= cnt;i++)
        if(dis[que[i].to]==dis[que[i].from]+que[i].v)
            que[i].flag = 1;
    printf("%lld\n", dis[n]);
    int left = 1, right = 1;
    ava[height[right].id] = 1;
    long long ans = inf;
    while(right<=n)
    {
        while(bfs(1,n) && left<right)
        {
            ans = min(ans, height[right].height - height[left].height);
            ava[height[left].id] = 0;
            left++;
        }
        right++;
        ava[height[right].id] = 1;
    }
    printf("%lld", ans);
    return 0;
}