1 条题解

  • 6
    @ 2021-9-5 9:24:50

    题意

    有一个 nn 个点 mm 条边的无向图,每个点有点权 hih_i,每条边有边权 wiw_i,让你找出一条从 11nn 的路径,在最小化路径长度的情况下最小化路径上最大点权和最小点权的差。

    $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}$

    分析

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

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

    代码

    这里提供来自出题人的 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;
    }
    
    • 1

    信息

    ID
    194
    时间
    1500ms
    内存
    128MiB
    难度
    5
    标签
    递交数
    95
    已通过
    31
    上传者