野猪路径规划问题（Wild Boar）题解

这道题的核心是在动态修改的节点序列中，寻找满足“不沿原路返回前一个到达节点”规则的最短路径总和。解题关键在于预处理图中特殊路径的最短距离，再用线段树维护动态序列的路径总和，平衡预处理复杂度与动态查询效率。

一、题目分析与核心规则

1. 问题背景

• 森林是含 (N) 个节点、(M) 条带权无向边的连通图，边无重复。
• 初始有长度为 (L) 的节点序列 (X_1,X_2,\dots,X_L)，JOI 需从 (X_1) 依次访问到 (X_L)。
• 每次修改将 (X_{P_k}) 改为 (Q_k)，需输出修改后“合法路径”的最短总长度（无法则输出 -1）。

2. 核心规则：合法路径的判定

关键约束是“不能沿原路返回前一个到达的节点”，即：

• 若从节点 (u) 经边 (e) 到达节点 (v)，则从 (v) 出发的下一条边不能是 (e)（原路返回）。
• 例如：从 (1) 经边 (e1) 到 (2)，则从 (2) 出发不能直接经 (e1) 回 (1)，但可经其他边（如 (e2) 到 (3)）后，再经 (e1) 回 (1)。

二、核心思路：预处理 + 动态维护

1. 问题拆解

整个路径可拆分为 (L-1) 段：(X_1 \to X_2)、(X_2 \to X_3)、…、(X_{L-1} \to X_L)。总长度是各段最短合法路径长度之和，因此：

• 预处理：提前计算任意两个节点 (u \to v) 的所有合法路径的最短距离（考虑路径首尾边的约束）。
• 动态维护：用线段树维护序列中相邻节点对的路径长度，支持单点修改（修改 (X_P) 会影响 (X_{P-1} \to X_P) 和 (X_P \to X_{P+1}) 两段），快速查询总和。

2. 预处理关键：路径的“状态”定义

由于合法路径受“前一条边”约束，需用“边”来定义路径状态：

• 定义 (L[e1][e2])：从边 (e1) 的终点出发，经合法路径到达边 (e2) 的起点，且路径不包含 (e1) 的反向边的最短长度。
  • 边 (e1) 是“进入当前节点的边”，边 (e2) 是“离开当前节点的边”，确保不原路返回。
• 进一步将边映射到节点对：对任意节点对 (u \to v)，预处理 4 种状态的最短距离（对应路径首尾边的不同约束），存储在 dis00、dis01、dis10、dis11 中，覆盖所有合法路径场景。

3. 动态维护关键：线段树

• 线段树每个叶子节点对应序列中相邻节点对 (X_i \to X_{i+1})，存储该节点对 4 种状态的最短距离。
• 线段树内部节点通过“合并”操作，计算两段路径拼接后的最短距离（确保前一段的尾边与后一段的头边满足合法约束）。
• 修改 (X_P) 时，只需更新叶子节点 (P-1) 和 (P)，再向上合并，即可快速得到新的总长度。

三、完整代码实现

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll N = 4005, M = 1e5 + 5, inf = 1e18;
int n, m, q, len;
int p1[N], p2[N], val[N], tot1 = 1;  // p1[e]:边e的起点，p2[e]:边e的终点，val[e]:边e的权值，tot1:边的总数（从2开始，1为占位）
ll dis00[2005][2005];  // 节点u→v的状态00最短距离：s00[u][v]是进入u的边，t00[u][v]是离开v的边
int s00[2005][2005], t00[2005][2005];  // s00[u][v]：u→v路径的起始边，t00[u][v]：u→v路径的结束边
ll dis01[2005][2005];  // 节点u→v的状态01最短距离
int s01[2005][2005], t01[2005][2005];
ll dis10[2005][2005];  // 节点u→v的状态10最短距离
int s10[2005][2005], t10[2005][2005];
ll dis11[2005][2005];  // 节点u→v的状态11最短距离
int s11[2005][2005], t11[2005][2005];
ll L[N][N];  // L[e1][e2]：从边e1的终点到边e2的起点的最短合法路径长度
ll dis[N][2];  // 迪杰斯特拉中节点u的两种最短距离：dis[u][0]是最优，dis[u][1]是次优
int las[N][2], vis[N][2];  // las[u][c]：到达u且状态为c的最后一条边；vis[u][c]：是否访问过
struct edge {
    int to, id, w;  // to：邻接节点，id：边的编号，w：边的权值
};
vector<edge> v[N];  // 图的邻接表：v[u]存储u的所有邻接边
struct node {
    ll dis;
    int pos, k1;  // pos：节点编号，k1：状态（0=最优，1=次优）
};
inline bool operator < (node x, node y) {  // 优先队列按距离从小到大排序（大根堆转小根堆）
    return x.dis > y.dis;
}
priority_queue<node> que;
inline void chx(ll &x, ll y) {  // 更新x为x和y的最小值
    x = min(x, y);
}
int pos[M];  // 节点序列X：pos[i] = X_i
struct qwq {  // 线段树节点存储的信息：4种状态的距离、起始边、结束边
    ll dis[2][2];
    int s[2][2], t[2][2];
} tree[M * 4];  // 线段树，大小为4*M（M是序列长度上限1e5）

// 检查两段路径的拼接是否合法：前一段的结束边t与后一段的起始边s是否满足“不原路返回”
bool check(int x, int y) {
    return ((x ^ y) >= 2);  // 边x和y不是反向边（反向边编号相差1，如e和e^1）
}

// 合并两个线段树节点x（左段）和y（右段），得到拼接后的节点z
qwq merge(qwq x, qwq y) {
    qwq z;
    // 初始化所有状态的距离为无穷大
    for (int i = 0; i < 2; i++)
        for (int j = 0; j < 2; j++)
            z.dis[i][j] = inf;

    // 合并状态00：左段任意状态 → 右段任意状态，取最短距离
    for (int p1 = 0; p1 < 2; p1++)
        for (int p2 = 0; p2 < 2; p2++)
            for (int p3 = 0; p3 < 2; p3++)
                for (int p4 = 0; p4 < 2; p4++)
                    if (check(x.t[p1][p2], y.s[p3][p4]))  // 左段尾边与右段头边合法
                        if (z.dis[0][0] > x.dis[p1][p2] + y.dis[p3][p4]) {
                            z.dis[0][0] = x.dis[p1][p2] + y.dis[p3][p4];
                            z.s[0][0] = x.s[p1][p2];  // 拼接后路径的起始边=左段起始边
                            z.t[0][0] = y.t[p3][p4];  // 拼接后路径的结束边=右段结束边
                        }

    // 合并状态11：在00基础上，额外约束起始边和结束边的唯一性（确保路径不重复）
    for (int p1 = 0; p1 < 2; p1++)
        for (int p2 = 0; p2 < 2; p2++)
            for (int p3 = 0; p3 < 2; p3++)
                for (int p4 = 0; p4 < 2; p4++)
                    if (check(x.t[p1][p2], y.s[p3][p4]))
                        if (check(z.s[0][0], x.s[p1][p2]))
                            if (check(z.t[0][0], y.t[p3][p4]))
                                if (z.dis[1][1] > x.dis[p1][p2] + y.dis[p3][p4]) {
                                    z.dis[1][1] = x.dis[p1][p2] + y.dis[p3][p4];
                                    z.s[1][1] = x.s[p1][p2];
                                    z.t[1][1] = y.t[p3][p4];
                                }

    // 合并状态10和01：混合约束起始边和结束边
    for (int p1 = 0; p1 < 2; p1++)
        for (int p2 = 0; p2 < 2; p2++)
            for (int p3 = 0; p3 < 2; p3++)
                for (int p4 = 0; p4 < 2; p4++)
                    if (check(x.t[p1][p2], y.s[p3][p4])) {
                        // 状态10：起始边满足11约束，结束边满足00约束
                        if (check(z.s[0][0], x.s[p1][p2]))
                            if (check(z.t[1][1], y.t[p3][p4]))
                                if (z.dis[1][0] > x.dis[p1][p2] + y.dis[p3][p4]) {
                                    z.dis[1][0] = x.dis[p1][p2] + y.dis[p3][p4];
                                    z.s[1][0] = x.s[p1][p2];
                                    z.t[1][0] = y.t[p3][p4];
                                }
                        // 状态01：起始边满足00约束，结束边满足11约束
                        if (check(z.s[1][1], x.s[p1][p2]))
                            if (check(z.t[0][0], y.t[p3][p4]))
                                if (z.dis[0][1] > x.dis[p1][p2] + y.dis[p3][p4]) {
                                    z.dis[0][1] = x.dis[p1][p2] + y.dis[p3][p4];
                                    z.s[0][1] = x.s[p1][p2];
                                    z.t[0][1] = y.t[p3][p4];
                                }
                    }

    return z;
}

#define lc k<<1        // 左孩子节点编号
#define rc k<<1|1      // 右孩子节点编号
#define ls lc,l,mid    // 左子树：节点k，区间[l,mid]
#define rs rc,mid+1,r  // 右子树：节点k，区间[mid+1,r]

// 线段树pushup：合并左右孩子信息到父节点
void pushup(int k) {
    tree[k] = merge(tree[lc], tree[rc]);
}

// 线段树单点更新：将第x个叶子节点（对应序列X_x→X_{x+1}）更新为最新的4种状态
void change(int k, int l, int r, int x) {
    if (l == r) {  // 叶子节点：对应X_l→X_{l+1}（即pos[l]→pos[l+1]）
        tree[k].dis[0][0] = dis00[pos[l]][pos[l+1]];
        tree[k].s[0][0] = s00[pos[l]][pos[l+1]];
        tree[k].t[0][0] = t00[pos[l]][pos[l+1]];
        tree[k].dis[0][1] = dis01[pos[l]][pos[l+1]];
        tree[k].s[0][1] = s01[pos[l]][pos[l+1]];
        tree[k].t[0][1] = t01[pos[l]][pos[l+1]];
        tree[k].dis[1][0] = dis10[pos[l]][pos[l+1]];
        tree[k].s[1][0] = s10[pos[l]][pos[l+1]];
        tree[k].t[1][0] = t10[pos[l]][pos[l+1]];
        tree[k].dis[1][1] = dis11[pos[l]][pos[l+1]];
        tree[k].s[1][1] = s11[pos[l]][pos[l+1]];
        tree[k].t[1][1] = t11[pos[l]][pos[l+1]];
        return ;
    }
    int mid = l + r >> 1;
    if (x <= mid)
        change(ls, x);
    else
        change(rs, x);
    pushup(k);  // 更新父节点
}

// 处理动态查询：初始化序列并响应T次修改
void work() {
    // 读入初始节点序列X
    for (ll i = 1; i <= len; i++)
        scanf("%d", &pos[i]);
    // 初始化线段树：每个叶子节点对应X_i→X_{i+1}（共len-1个）
    for (ll i = 1; i < len; i++)
        change(1, 1, len - 1, i);
    
    ll ans = inf;
    while (q--) {  // 处理T次修改查询
        ll x, y;
        scanf("%lld%lld", &x, &y);
        pos[x] = y;  // 修改X_x为y
        ans = inf;
        // 修改会影响X_{x-1}→X_x和X_x→X_{x+1}两段，需更新对应叶子节点
        if (x >= 2)
            change(1, 1, len - 1, x - 1);
        if (x < len)
            change(1, 1, len - 1, x);
        // 取4种状态中的最短距离作为答案
        for (int i = 0; i < 2; i++)
            for (int j = 0; j < 2; j++)
                chx(ans, tree[1].dis[i][j]);
        // 输出结果：若距离为无穷大则输出-1，否则输出距离
        if (ans >= inf)
            puts("-1");
        else
            printf("%lld\n", ans);
    }
}

int main() {
    // 读入N（节点数）、M（边数）、T（修改次数）、len（序列长度L）
    scanf("%d%d%d%d", &n, &m, &q, &len);
    // 读入M条边，构建邻接表（无向边拆分为两条有向边，编号连续）
    for (int i = 1, x, y, z; i <= m; i++) {
        scanf("%d%d%d", &x, &y, &z);
        tot1++;  // 边编号从2开始（1为占位）
        p1[tot1] = x, p2[tot1] = y, val[tot1] = z;
        v[x].push_back(edge{y, tot1, z});  // x→y的边，编号tot1
        tot1++;
        p1[tot1] = y, p2[tot1] = x, val[tot1] = z;
        v[y].push_back(edge{x, tot1, z});  // y→x的边，编号tot1（与上一条反向）
    }

    //