题解：P14376 [JOISC 2018] 野猪 / Wild Boar

R_shuffle · 2025-11-18 21:14:34 · 题解

考虑怎么直接在点之间转移，如果没有不能走回头路的限制，显然就是直接走最短路。问题在于怎么处理回头路的限制。

不妨先考虑相邻的四个点之间夹的三条路径，不妨设为 A,B,C,D，则 A\to B 和 C\to D 会给 B\to C 带来两条限制，分情况讨论一下：

所以实际上把这四种路径求出来就能覆盖所有的情况了。

不难发现限制都是对边的，所以考虑把边之间的最短路求出来。注意转移的时候不要走回头路，Dijkstra 的复杂度就是 O(m^2\log m) 的。

然后考虑对于每对点都求出来上述的四种边，复杂度显然是 O(\sum\limits_{u\neq v}deg_udeg_v)\leq \frac{n-1}{2n}O((sum deg_u)^2)=O(m^2) 的。

所以就只用关心两点之间走的是那条路径，可以写成矩阵的 (\min,+) 的形式，线段树维护。

#include<bits/stdc++.h>
using namespace std;
#define __MY_TEST__ 0
#define int long long
inline int read()
{
    int re=0,f=1;
    char ch=getchar();
    while(!isdigit(ch)){if(ch=='-') f=-1; ch=getchar();}
    while( isdigit(ch)) re=(re<<3)+(re<<1)+(ch^48),ch=getchar();
    return re*f;
}
const int N=4005,L=2e5+5;
int n,m,t,l;
struct Edge
{
    int u,v,w;
}e[N];
namespace Dijkstra
{

int dis[4005][4005];
int head[N],to[N<<1],acc[N<<1],nxt[N<<1],tot=-1;
void add(int u,int v,int w)
{
    to[++tot]=v;
    acc[tot]=w;
    nxt[tot]=head[u];
    head[u]=tot;
}
void dijkstra(int s)
{
    for(int i=0;i<=tot;i++) dis[s][i]=1e18;
    priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >q;
    q.emplace(dis[s][s]=acc[s],s);
    while(!q.empty())
    {
        auto dq=q.top();
        q.pop();
        if(dq.first!=dis[s][dq.second]) continue;
        for(int i=head[to[dq.second]];~i;i=nxt[i])
        {
            if((i^dq.second)==1) continue;
            int w=acc[i];
            if(dis[s][i]>dq.first+w)
            {
                dis[s][i]=dq.first+w;
                q.emplace(dis[s][i],i);
            }
        }
    }
}
void get_dis()
{
    for(int i=1;i<=n;i++) head[i]=-1;
    for(int i=1;i<=m;i++)
    {
        int u=e[i].u,v=e[i].v,w=e[i].w;
        add(u,v,w);
        add(v,u,w);
    }
    for(int i=0;i<=tot;i++) dijkstra(i);
}

}
using namespace Dijkstra;
vector<int>vec[N];
pair<int,int>ce[N][N][4];
int X[L];
struct Matrix
{
    int a[4][4];
    Matrix()
    {
        for(int i=0;i<4;i++) for(int j=0;j<4;j++) a[i][j]=1e18;
    }
}tr[L<<2];
Matrix operator *(const Matrix &x,const Matrix &y)
{
    Matrix re;
    for(int i=0;i<4;i++) for(int j=0;j<4;j++) for(int k=0;k<4;k++) re.a[i][j]=min(re.a[i][j],x.a[i][k]+y.a[k][j]);
    return re;
}
Matrix init(int pos)
{
    Matrix re;
    int u=X[pos-1],v=X[pos],w=X[pos+1];
    for(int i=0;i<4;i++) for(int j=0;j<4;j++)
    {
        auto p1=ce[u][v][i],p2=ce[v][w][j];
        if(!~p1.first||!~p2.first) continue;
        if((p1.second^p2.first)==1) continue;
        re.a[i][j]=dis[p2.first][p2.second];
    }
    return re;
}
void build(int num,int l,int r)
{
    if(l==r)
    {
        tr[num]=init(l);
        return ;
    }
    int mid=(l+r)>>1;
    build(num*2,l,mid);
    build(num*2+1,mid+1,r);
    tr[num]=tr[num*2]*tr[num*2+1];
}
void modify(int num,int l,int r,int pos)
{
    if(l==r)
    {
        tr[num]=init(l);
        return ;
    }
    int mid=(l+r)>>1;
    if(pos<=mid) modify(num*2,l,mid,pos);
    else modify(num*2+1,mid+1,r,pos);
    tr[num]=tr[num*2]*tr[num*2+1];
}
pair<int,int>get(int u,int v,int b1,int b2)
{
    pair<int,int>re={-1,-1};
    for(int i=head[u];~i;i=nxt[i]) for(int j=head[v];~j;j=nxt[j])
    {
        if(i!=b1&&(j^1)!=b2&&(re.first==-1||dis[i][j^1]<dis[re.first][re.second])) re={i,j^1};
    }
    return re;
}
signed main(){
#if __MY_TEST__
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
#endif
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    n=read(),m=read(),t=read(),l=read();
    for(int i=1;i<=m;i++) e[i].u=read(),e[i].v=read(),e[i].w=read();
    get_dis();
    for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(i!=j)
    {
        ce[i][j][0]=get(i,j,-1,-1);
        ce[i][j][1]=get(i,j,ce[i][j][0].first,ce[i][j][0].second);
        ce[i][j][2]=get(i,j,ce[i][j][1].first,ce[i][j][0].second);
        ce[i][j][3]=get(i,j,ce[i][j][0].first,ce[i][j][1].second);
    }
    // for(int i=0;i<=tot;i++) for(int j=0;j<=tot;j++) cerr<<dis[i][j]<<" \n"[j==tot];
    // cerr<<dis[1][4]<<'\n';
    // for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) cerr<<i<<' '<<j<<' '<<ce[i][j][0].first<<' '<<ce[i][j][0].second<<'\n';
    // cerr<<'\n';
    // for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) cerr<<i<<' '<<j<<' '<<ce[i][j][1].first<<' '<<ce[i][j][1].second<<'\n';
    // cerr<<'\n';
    // for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) cerr<<i<<' '<<j<<' '<<ce[i][j][2].first<<' '<<ce[i][j][2].second<<'\n';
    // cerr<<'\n';
    // for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) cerr<<i<<' '<<j<<' '<<ce[i][j][3].first<<' '<<ce[i][j][3].second<<'\n';
    for(int i=1;i<=l;i++) X[i]=read();
    if(l==2)
    {
        while(t--)
        {
            int x=read(),v=read();
            X[x]=v;
            auto p=ce[X[1]][X[2]][0];
            cout<<dis[p.first][p.second]<<'\n';
        }
    }
    else
    {
        build(1,2,l-1);
        while(t--)
        {
            int x=read(),v=read();
            X[x]=v;
            if(x-1>=2) modify(1,2,l-1,x-1);
            if(x>=2&&x<l) modify(1,2,l-1,x);
            if(x+1<l) modify(1,2,l-1,x+1);
            int ans=1e18;
            for(int i=0;i<4;i++) for(int j=0;j<4;j++)
            {
                auto p=ce[X[1]][X[2]][i];
                ans=min(ans,dis[p.first][p.second]+tr[1].a[i][j]);
                cerr<<tr[1].a[i][j]<<" \n"[j==3];
            }
            cout<<(ans<1e18?ans:-1)<<'\n';
        }
    }
}