题解：P16397 [ECUSTPC 2026 Spring] 右灯左行

· · 题解

题意简述

河流两岸各有 n 个站点。相邻两列之间形成一条有向带权环线。给定每条环线的方向和四条边权，回答任意两个站点之间的最短路。

解题思路

每条环线横跨相邻两列。向右穿过第 i 条环线时，只有一条横向边可用。方向为 O 时走北岸，方向为 I 时走南岸。向左穿过它时，所在岸恰好相反。

边权非负，所以一定存在不重复经过站点的最短路。若起点列 x<y，路径依次向右跨过中间各列。每次跨越列间切口时，可用的向右边唯一。因此，除同列换岸外，整条路径的走法被各环线方向完全确定。

先预处理向右行走的两个距离势能。R_i^{\mathrm{out}} 表示到达第 i 列向右出发点的累计距离。R_i^{\mathrm{in}} 表示到达第 i 列左侧入点的累计距离。令 R_1^{\mathrm{out}}=0。

穿过第 i 条环线后：

R_{i+1}^{\mathrm{in}}=R_i^{\mathrm{out}}+ \begin{cases} u_i & s_i=\texttt{O} \\ d_i & s_i=\texttt{I} \end{cases}

若相邻两条环线方向相同，入点就是下一条环线的出发点。若方向不同，则需要在第 i+1 列换岸。此时相邻两条环线各提供一条方向正确的竖边，可以选择较便宜的一条：

R_{i+1}^{\mathrm{out}}=R_{i+1}^{\mathrm{in}}+ \begin{cases} 0 & s_i=s_{i+1} \\ \min(r_i,l_{i+1}) & s_i\ne s_{i+1} \end{cases}

于是，从第 x 列的向右出发点到第 y 列的左侧入点，费用就是：

R_y^{\mathrm{in}}-R_x^{\mathrm{out}}

从右向左完全对称。令 L_i^{\mathrm{out}} 表示第 i 列向左出发点的累计势能。L_i^{\mathrm{in}} 表示第 i 列右侧入点的累计势能。从 L_n^{\mathrm{out}}=0 开始倒序递推：

L_i^{\mathrm{in}}=L_{i+1}^{\mathrm{out}}+ \begin{cases} d_i & s_i=\texttt{O} \\ u_i & s_i=\texttt{I} \end{cases}

相邻方向改变时，同样增加 \min(l_i,r_{i-1})。从第 x 列向左出发点到第 y 列右侧入点的费用为 L_y^{\mathrm{in}}-L_x^{\mathrm{out}}。

还需要知道每一列的两个换岸代价。记：

\begin{aligned} D_i & =\operatorname{dist}(N_i,S_i) \\ U_i & =\operatorname{dist}(S_i,N_i) \end{aligned}

把方向连续相同的环线合并成极大区间 [l,r]。同向区间内，北岸和南岸的行驶方向分别固定且相反。一个不含环的同列换岸路径只会选择一条方向正确的竖边，其余路段随之唯一确定。

以方向 O 的区间为例。计算 D_i 时，路径可以直接使用左侧环线的向下竖边。另一种选择是沿北岸向右，到下一列换岸后再沿南岸返回。因此，从右向左递推：

D_i=\min(r_{i-1},u_i+D_{i+1}+d_i)

区间边界不存在的项直接忽略。在最右列 r+1，可选择 r_r，若右侧还有反向环线，也可选择 l_{r+1}。

计算 U_i 时，方向相反。路径可以直接使用右侧环线的向上竖边，或先向左绕到前一列。因此，从左向右递推：

U_i=\min(l_i,d_{i-1}+U_{i-1}+u_{i-1})

方向 I 时，上述两个递推方向互换。D_i 从左向右计算，U_i 从右向左计算。每个环线只属于一个极大同向区间，所以全部换岸代价可在线性时间内求出。

回答询问时分三种情况。

若 x=y，同岸答案为 0；北岸到南岸取 D_x，南岸到北岸取 U_x。

若 x<y，先判断起点是否位于第 x 条环线的向右出发岸。若不在，就加上 D_x 或 U_x。然后加上主干距离 R_y^{\mathrm{in}}-R_x^{\mathrm{out}}。最后根据第 y-1 条环线的到达岸，补上终点列的换岸代价。

若 x>y，使用向左势能作完全对称的计算。

预处理会线性扫描环线与同向区间，每个询问只进行常数次判断。因此，总时间复杂度为 O(n+q)，空间复杂度为 O(n)。

正确性证明

先证明跨列主干唯一。任意不含环的路径从第 x 列走到第 y 列时，都必须依次跨过中间切口。

每个切口在指定方向上只有一条横向边。因此，经过的岸和边权都被唯一确定。

相邻环线方向变化时，路径必须在公共列换岸。两条相邻竖边都能完成这一步，取较小边权即可。故势能差准确给出两个主干端点之间的最短距离。

再证明换岸递推。一个极大同向区间内，两岸的方向相反。简单路径一旦选定换岸竖边，换岸前后的横向路径均被唯一确定。

递推枚举立即换岸和跨过一个环后再换岸两种可能，因而覆盖区间内每一条简单换岸路径。边界处再加入相邻反向环线的竖边，便得到全图中的最小换岸代价。

最后，不同列询问的简单最短路能唯一拆成起点换岸、跨列主干和终点换岸三段。

两段换岸使用 D,U 的最小值，主干使用势能差。

三段均为各自端点间的最短路径，连接后也是合法路径。因此，询问答案等于全图最短路。

参考代码

#include <bits/stdc++.h>
using namespace std;

using ll=long long;
const int N=100005;
const ll inf=0x3f3f3f3f3f3f3f3f;
int n,q;
int u[N],d[N],l[N],r[N];
ll dn[N],up[N],ri[N],ro[N],li[N],lo[N];
string s;
void vertical(int x,int y)
{
    if(s[x]=='O')
    {
        dn[y+1]=min(dn[y+1],(ll)r[y]);
        if(y<n-1)dn[y+1]=min(dn[y+1],(ll)l[y+1]);
        for(int i=y;i>=x;i--)
        {
            if(i>x)dn[i]=min(dn[i],(ll)r[i-1]);
            dn[i]=min(dn[i],dn[i+1]+u[i]+d[i]);
        }
        up[x]=min(up[x],(ll)l[x]);
        if(x>1)up[x]=min(up[x],(ll)r[x-1]);
        for(int i=x+1;i<=y+1;i++)
        {
            if(i<=y)up[i]=min(up[i],(ll)l[i]);
            up[i]=min(up[i],up[i-1]+u[i-1]+d[i-1]);
        }
    }
    else if(s[x]=='I')
    {
        dn[x]=min(dn[x],(ll)l[x]);
        if(x>1)dn[x]=min(dn[x],(ll)r[x-1]);
        for(int i=x+1;i<=y+1;i++)
        {
            if(i<=y)dn[i]=min(dn[i],(ll)l[i]);
            dn[i]=min(dn[i],dn[i-1]+u[i-1]+d[i-1]);
        }
        up[y+1]=min(up[y+1],(ll)r[y]);
        if(y<n-1)up[y+1]=min(up[y+1],(ll)l[y+1]);
        for(int i=y;i>=x;i--)
        {
            if(i>x)up[i]=min(up[i],(ll)r[i-1]);
            up[i]=min(up[i],up[i+1]+u[i]+d[i]);
        }
    }
}
void solve()
{
    cin>>n>>q;
    for(int i=1;i<n;i++)
    {
        cin>>u[i]>>d[i]>>l[i]>>r[i];
    }
    cin>>s;
    s=' '+s;
    fill(dn+1,dn+n+1,inf);
    fill(up+1,up+n+1,inf);
    for(int i=1;i<n;)
    {
        int j=i;
        while(j+1<n&&s[j+1]==s[i])j++;
        vertical(i,j);
        i=j+1;
    }
    ro[1]=0;
    for(int i=1;i<n;i++)
    {
        ri[i+1]=ro[i]+(s[i]=='O'?u[i]:d[i]);
        if(i+1<n)ro[i+1]=ri[i+1]+(s[i]==s[i+1]?0:min(r[i],l[i+1]));
    }
    lo[n]=0;
    for(int i=n-1;i;i--)
    {
        li[i]=lo[i+1]+(s[i]=='O'?d[i]:u[i]);
        if(i>1)lo[i]=li[i]+(s[i]==s[i-1]?0:min(l[i],r[i-1]));
    }
    while(q--)
    {
        char a,b;
        int x,y;
        cin>>a>>x>>b>>y;
        int c=a=='S',e=b=='S';
        if(x==y)
        {
            if(c==e)cout<<0<<'\n';
            else cout<<(c?up[x]:dn[x])<<'\n';
        }
        else if(x<y)
        {
            int st=s[x]=='I',ed=s[y-1]=='I';
            ll ans=ri[y]-ro[x];
            if(c!=st)ans+=c?up[x]:dn[x];
            if(e!=ed)ans+=e?dn[y]:up[y];
            cout<<ans<<'\n';
        }
        else if(x>y)
        {
            int st=s[x-1]=='O',ed=s[y]=='O';
            ll ans=li[y]-lo[x];
            if(c!=st)ans+=c?up[x]:dn[x];
            if(e!=ed)ans+=e?dn[y]:up[y];
            cout<<ans<<'\n';
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin>>T;
    while(T--)solve();
    return 0;
}