1 条题解

  • 0
    @ 2026-5-10 21:07:00

    P3238 [HNOI2014]道路堵塞

    前言

    基于打破题解区被 SPFA 算法霸凌的局面，对无人问津的 Dijkstra 思路的代码实现，即对

    https://www.luogu.com.cn/user/124918 "LinkyChristian"

    顺便提供一个双倍经验：CF1163F Indecisive Taxi Fee。

    题目

    给定一个 nn 个点 mm 条单向边的有向图，还给定了 1→n{1}\to{n} 最短路径经过的边的编号。每次询问（询问间相互独立）删去最短路径上的一条边后，新的 1→n{1}\to{n} 最短路径是多少？

    Solution

    变量解释

    原最短路径：题目中给定的最短路径。

    原编号：题目输入的边的顺序的编号。

    新编号：对原最短路径上的边重新编号，具体编号方式见下述。

    • disx,ydis_{x,y}：x→y{x}\to{y} 的最短路径长度。

    • IxI_{x}：原编号为 xx 的边是否在最短路径上：若为 00，则代表不在；否则，由 1→n{1}\to{n} 的原最短路径经过的边依次从大到小 [l,1][l,1] 重新编号。记 [1,l][1,l] 的编号为新编号。

    • LxL_x：从 xx 点连出的最小的原最短路径上的边的新编号。

    • RxR_x：从原最短路径上的边连入 xx 点最大的新编号。

    思路

    首先有个很显然的结论，对于必须经过一条连接着 x→y{x}\to{y} 的单向边，权值为 w(x,y)w(x,y)，1→n{1}\to{n} 的最短路径长度为：

    dis1,n=dis1,x+w(x,y)+disy,ndis_{1,n}=dis_{1,x}+w(x,y)+dis_{y,n}

    此时就要使用到上述的变量 Lx,RxL_x,R_x。根据变量的定义，必须经过 xx 点的最短路径是不经过 [Lx+1,Rx−1][L_x+1,R_x-1] 这段新编号区间的边的，换句话说就是绕过了这一段原最短路径上的边。

    那再转化到边上，对于一条非原最短路径上的边连接着 x→y{x}\to{y}，我们就需要更新 [Ly+1,Rx−1][L_y+1,R_x-1] 这段区间的权值为 dis1,x+w(x,y)+disy,ndis_{1,x}+w(x,y)+dis_{y,n}。

    翻译一下就是：连入 xx 的原最短路径上的边和从 yy 连出的原最短路径上的边，他们之间的原最短路径上的边是可以不用经过的，那不经过这段原最短路径上的边的权值就可以更新为 dis1,x+w(x,y)+disy,ndis_{1,x}+w(x,y)+dis_{y,n}。

    最后查询时就是每次查询不经过某一条原最短路径上的边，新的最短路径最小值。

    解法

    现在要求这些变量：

    最短路径长度

    dis1,xdis_{1,x}：11 到任意点的最短路径。这个好处理，直接沿着正边从 11 跑一遍 Dijkstra 最短路径就可以求出。

    disx,ndis_{x,n}：任意点到 nn 的最短路径。建立反图，沿着反边从 nn 跑一遍 Dijkstra 最短路径就可以求出。

    连入及连出某一点的原最短路径上的边的新编号

    LxL_x：因为要求最小值，初始化为极大值，LnL_n 初始为 00。从 nn 出发，沿反图跑最短路径。设当前点为 uu，其可以到达的节点为 vv，然后从 II 和 LuL_u 更新：若 II 不是原最短路径上的边，只能从 LuL_u 更新；否则从 II 转移。

    RxR_x：因为要求最大值，初始化为极小值，R1R_1 初始为 l+1l+1。从 11 出发，沿原图跑最短路径。设当前点为 uu，其可以到达的节点为 vv，然后从 II 和 RuR_u 更新：若 II 不是原最短路径上的边，只能从 LuL_u 更新；否则从 II 转移。

    Code 参考：

    处理 RR，跑原图：

    if (dis[v] == dis[u] + e[i].w) // 路径权值相同就取 max
{
    if (I[i]) // 是原最短路径边直接转移
        R[v] = max(R[v], I[i]);
    else // 否则只能继承
        R[v] = max(R[v], R[u]);
}
if (dis[v] > dis[u] + e[i].w) // 路径更优直接覆盖
{
    if (I[i]) // 是原最短路径边直接转移
        R[v] = I[i];
    else // 否则只能继承
        R[v] = R[u];
    dis[v] = dis[u] + e[i].w;
}

    处理 LL，跑反图：

    if (dis[v] == dis[u] + e[i].w) // 路径权值相同就取 min
{
    if (I[i]) // 是原最短路径边直接转移
        L[v] = min(L[v], I[i]);
    else // 否则只能继承
        L[v] = min(L[v], L[u]);
}
if (dis[v] > dis[u] + e[i].w) // 路径更优直接覆盖
{
    if (I[i]) // 是原最短路径边直接转移
        L[v] = I[i];
    else // 否则只能继承
        L[v] = L[u];
    dis[v] = dis[u] + e[i].w;
}

    不经过某条原最短路径上的边的新 1→n{1}\to{n} 最短路径最小值

    已经求出了 LL 和 RR，只要枚举所有的正边，这条正边连接 x→yx\to y，把 [Ly+1,Rx−1][L_y+1,R_x-1] 这段区间的权值更新为 dis1,x+w(x,y)+disy,ndis_{1,x}+w(x,y)+dis_{y,n}。也就是一个区间取 min⁡\min 操作，用线段树维护最小值，区间修改，单点查询。

    Code 参考：

    显然用线段树维护最小值，区间修改，单点查询这段代码很简单，直接跳过就行了。

    namespace Segment
{
    #define lc(i) (i << 1)
    #define rc(i) (i << 1 | 1)
    #define lmid ((l + r) >> 1)
    #define rmid ((l + r + 2) >> 1)
    int tr[N << 2]， tag[N << 2];
    inline void change(const int &i, const int &val)
    {
        tr[i] = min(tr[i], val);
        tag[i] = min(tag[i], val);
    }
    inline void push_down(const int &i)
    {
        if (tag[i] != INF)
        {
            change(lc(i), tag[i]);
            change(rc(i), tag[i]);
            tag[i] = INF;
        }
    }
    inline void update(int i, int l, int r, int cl, int cr, int val)
    {
        if (l > cr || r < cl) return void();
        if (l >= cl && r <= cr) return change(i, val);
        push_down(i);
        update(lc(i), l, lmid, cl, cr, val);
        update(rc(i), rmid, r, cl, cr, val);
    }
    inline int query(int i, int l, int r, int x)
    {
        if (l == r) return tr[i];
        push_down(i);
        if (x <= lmid) return query(lc(i), l, lmid, x);
        if (x >= rmid) return query(rc(i), rmid, r, x);
    }
}
using namespace Segment;

    疑问

    Q：但是为什么要 LxL_x 尽量小，RxR_x 尽量大呢？

    A:LL 越小 RR 越大，更新的值域就越大，更新的越多，答案自然就会更优，因此我们让他尽量绕过更多的原最短路径上的边。

    Code

    删去了一些基础内容，保留了代码框架。完整代码：click here.

    #include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 1e5 + 5;
namespace IO{/*Quick Read and Write*/}
using namespace IO;
namespace chain{/*链式前向星*/}
using namespace chain;
namespace Segment/*维护区间最小值*/
{
    inline void update(int i, int l, int r, int cl, int cr, int val){}
    inline int query(int i, int l, int r, int x){}
}
using namespace Segment;
struct type
{
    int x;
    int y;
    friend bool operator<(const type &A, const type &B){return A.y > B.y;}
    type(int x = 0, int y = 0) : x(x), y(y){}
};
int n, m, k;
int rode[N];
int I[N << 2], L[N], R[N];
int dis1[N], dis2[N];
bool vis[N];
inline void dij(int s, int *dis) // 代码核心，求 L,R
{
    priority_queue<type> q;
    memset(vis, false, sizeof(vis));
    dis[s] = 0;
    if (s == n)
        fill(L + 1, L + n + 1, k + 1), L[s] = 0;
    if (s == 1)
        fill(R + 1, R + n + 1, 0), R[s] = k + 1;
    q.push(type(s, 0));
    while (!q.empty())
    {
        int u = q.top().x;
        q.pop();
        if (vis[u])
            continue;
        vis[u] = true;
        for (int i = head[u]; i; i = e[i].nxt)
        {
            if ((i & 1) ^ (s == n)) // 判正反边
                continue;
            int v = e[i].v, ID = I[i] ? I[i] : (k + 1) * (s == 1);
            /*这里为了减少些 if，所以这样写，其实和上面的参考代码里 if 分类讨论时等价的。*/
            if (dis[v] == dis[u] + e[i].w)
            {
                if (R[v] < min(R[u], ID) && s == 1)
                    R[v] = min(R[u], ID);
                if (L[v] > max(L[u], ID) && s == n)
                    L[v] = max(L[u], ID);
            }
            if (dis[v] > dis[u] + e[i].w)
            {
                if (s == 1)
                    R[v] = min(R[u], ID);
                if (s == n)
                    L[v] = max(L[u], ID);
                dis[v] = dis[u] + e[i].w;
                q.push(type(v, dis[v]));
            }
        }
    }
}
signed main()
{
    memset(dis1, 0x3f, sizeof(dis1));
    memset(dis2, 0x3f, sizeof(dis2));
    read(n, m, k);
    for (int i = 1, u, v, w; i <= m; i++)
    {
        read(u, v, w);
        add(u, v, w);
        add(v, u, w);
    }
    for (int i = 1; i <= k; i++)
    {
        read(rode[i]);
        I[(rode[i] << 1)] = I[(rode[i] << 1) ^ 1] = k - i + 1; // 从大到小编号。
    }
    dij(1, dis1); //原图。
    dij(n, dis2); //反图。
    for (int i = 2; i <= ecnt; i += 2) // 只枚举正边。
    {
        if (I[i]) continue;
        int u = e[i].u, v = e[i].v;
        if (L[v] + 1 <= R[u] - 1)
            update(1, 1, k, L[v] + 1, R[u] - 1, dis1[u] + e[i].w + dis2[v]); //更新区间最小值
    }
    for (int i = 1; i <= k; i++)
    {
        int ans = query(1, 1, k, I[rode[i] << 1]); // 查询不走当前边的最短路径
        write(ans == 0x3f3f3f3f ? -1 : ans, '\n');
    }
    return 0;
}

    后言

    冒昧地指出

    https://www.luogu.com.cn/user/124918 &quot;LinkyChristian&quot;
    一个小错误：本题为有向图，而 CF1163F Indecisive Taxi Fee 为无向图，所以枚举边时不能用反边更新，只能用正边更新。也就是不能用 dis1,y+w(y,x)+disx,ndis_{1,y}+w(y,x)+dis_{x,n} 更新 [Lx+1,Ry−1][L_x+1,R_y-1] 这段区间。否则，这题就 Wrong 了，成功 get 2020 分。而且，这个做法跑了 290ms⁡290\operatorname{ms} 左右。

    辛苦管理员的审核，有问题可以指出，极力改正。

    • 1

    [HNOI2014] 道路堵塞

    信息

    ID
    5240
    时间
    1000ms
    内存
    256MiB
    难度
    10
    标签
    递交数
    2
    已通过
    2
    上传者
    1. Language
    2. 兼容模式
    3. 主题
    3. Worker 0, 9ms
    4. Powered by Hydro v5.0.1 Community