[loj2842]野猪

首先,并不一定走“除了上一次来的边”以外的最短路,但考虑“除了上一次来的边”以外的最短路和次短路(这里的次短路指最后一条边与最短路不同的“最短路”),必然是走这两者之一

(”除了上一次来的边“指第一步不走上一次来的边)

证明很显然,因为如果最短路不好必然是因为下一次需要先走最短路那条边,那么这次走次短路即可

但由于我们所预处理的并不能与实际的$X_{i}$有关(会有修改),但可以发现对于很多“上一次来的边”,其最短路和次短路都是一样的

具体来说,对于两点,求出:

1.最短路(任意一条,以下省略)

2.与最短路最后一条边不同的“最短路”

3.与最短路最后一条边不同且与第2条路径第一条边不同的“最短路”

4.与最短路第一条边的不同的“最短路”

5.与最短路第一条边不同且与第4条路径最后一条边不同的“最短路”

(前两个是用来查询除去的边没有用的情况,然后除去的边与次短路相同时修改次短路为第3条,除去的边与最短路相同时采用第4和第5条)

最短路的记录用第一条边、最后一条边的编号以及长度来描述最短路即可

事实上,这些都可以用$f_{i,j}$表示由第一次经过第$i$条边、最后一次经过第$j$条边(无向边拆为两条有向边来做)的最短路长度来处理,即枚举两点以及两边(总共$o(m^{2})$)

(有一个细节,就是要特殊处理存在直接路径的点对)

关于如何求$f_{i,j}$只需要把边当作点去求dijkstra即可,具体来说就是将原来的标记点改为标记边即可,但这样每一个边都做一次最坏会变为$o(m^{2})$,考虑到最短边仅仅只是自己的反向边没有更新,只需要用第二次搜到的边更新最短边的反向边即可

接下来用$dp_{i,j}$表示走到$X_{i}$且上一次选择的是第$j$种路径,根据上述信息不难转移

修改用线段树来维护这个dp,即对每一个区间维护一个5*5的矩阵表示$X_{l}$到$X_{l 1}$和$X_{r-1}$到$X_{r}$分别使用了什么路径,合并枚举$X_{mid}$到$X_{mid 1}$的路径即可

时间复杂度为$o(m^{2}\log_{2}m 5^{3}T\log_{2}L)$,可以通过

1 #include<bits/stdc  .h>  2 using namespace std;  3 #define N 2005  4 #define M 4005  5 #define ll long long  6 #define oo (1LL<<60)  7 #define T 100005  8 #define L (k<<1)  9 #define R (L 1) 10 #define mid (l r>>1) 11 struct ji{ 12     int nex,to,len; 13 }edge[M]; 14 struct path{ 15     int x,y; 16     ll d; 17     bool operator < (const path &k)const{ 18         return d<k.d; 19     } 20 }f[5][N][N]; 21 struct mat{ 22     int l,r,len; 23     ll a[5][5]; 24     path fl[5],fr[5]; 25 }o,tr[T<<2]; 26 priority_queue<pair<ll,int> >q; 27 int E,n,m,t,l,x,y,z,head[N],vis[M],visV[N]; 28 ll ans,d[M],dis[M][M]; 29 void add(int x,int y,int z){ 30     edge[E].nex=head[x]; 31     edge[E].to=y; 32     edge[E].len=z; 33     head[x]=E  ; 34 } 35 void dij(int k){ 36     memset(d,0x3f,sizeof(d)); 37     memset(vis,0,sizeof(vis)); 38     memset(visV,-1,sizeof(visV)); 39     d[k]=edge[k].len; 40     q.push(make_pair(-d[k],k)); 41     while (!q.empty()){ 42         k=q.top().second; 43         q.pop(); 44         if (vis[k])continue; 45         vis[k]=1; 46         x=edge[k].to; 47         if (visV[x]<0){ 48             visV[x]=(k^1); 49             for(int i=head[x];i!=-1;i=edge[i].nex) 50                 if (((k^i)!=1)&&(d[i]>d[k] edge[i].len)){ 51                     d[i]=d[k] edge[i].len; 52                     q.push(make_pair(-d[i],i)); 53                 } 54         } 55         else{ 56             y=visV[x]; 57             if (d[y]>d[k] edge[y].len){ 58                 d[y]=d[k] edge[y].len; 59                 q.push(make_pair(-d[y],y)); 60             } 61         } 62     } 63 } 64 mat merge(mat x,mat y){ 65     if (!x.len)return y; 66     if (!y.len)return x; 67     o.l=x.l,o.r=y.r,o.len=x.len y.len; 68     memcpy(o.fl,x.fl,sizeof(o.fl)); 69     memcpy(o.fr,y.fr,sizeof(o.fr)); 70     memset(o.a,0x3f,sizeof(o.a)); 71     if (x.len==1){ 72         for(int i=0;i<5;i  ){ 73             o.fl[i]=f[i][x.l][y.l]; 74             o.a[i][i]=f[i][x.r][y.l].d; 75         } 76     } 77     else{ 78         for(int i=0;i<5;i  ) 79             for(int j=0;j<5;j  ) 80                 for(int k=0;k<5;k  ) 81                     if ((x.fr[j].y^f[k][x.r][y.l].x)!=1) 82                         o.a[i][k]=min(o.a[i][k],x.a[i][j] f[k][x.r][y.l].d); 83     } 84     memcpy(x.a,o.a,sizeof(o.a)); 85     memset(o.a,0x3f,sizeof(o.a)); 86     if (y.len==1){ 87         for(int i=0;i<5;i  ){ 88             o.fr[i]=f[i][x.r][y.r]; 89             o.a[i][i]=0; 90         } 91     } 92     else{ 93         for(int i=0;i<5;i  ) 94             for(int j=0;j<5;j  ) 95                 for(int k=0;k<5;k  ) 96                     if ((f[i][x.r][y.l].y^y.fl[j].x)!=1) 97                         o.a[i][k]=min(o.a[i][k],y.a[j][k]); 98     } 99     memcpy(y.a,o.a,sizeof(o.a));100     memset(o.a,0x3f,sizeof(o.a));101     for(int i=0;i<5;i  )102         for(int j=0;j<5;j  )103             for(int k=0;k<5;k  )o.a[i][k]=min(o.a[i][k],x.a[i][j] y.a[j][k]);104     return o;105 }106 void update(int k,int l,int r,int x,int y){107     if (l==r){108         tr[k].l=tr[k].r=y;109         tr[k].len=1;110         return;111     }112     if (x<=mid)update(L,l,mid,x,y);113     else update(R,mid 1,r,x,y);114     tr[k]=merge(tr[L],tr[R]);115 }116 int main(){117     scanf("%d%d%d%d",&n,&m,&t,&l);118     memset(head,-1,sizeof(head));119     for(int i=1;i<=m;i  ){120         scanf("%d%d%d",&x,&y,&z);121         add(x,y,z);122         add(y,x,z);123     }124     for(int i=1;i<=n;i  )125         for(int j=1;j<=n;j  )126             for(int k=0;k<5;k  )127                 if (i==j)f[k][i][j]=path{-1,-1,0};128                 else f[k][i][j]=path{-1,-1,oo};129     for(int i=0;i<E;i  ){130         dij(i);131         for(int j=0;j<E;j  )dis[i][j]=d[j];132     }133     for(int i=1;i<=n;i  )134         for(int j=1;j<=n;j  ){135             for(int x=head[i];x!=-1;x=edge[x].nex){136                 if (edge[x].to==j)f[0][i][j]=min(f[0][i][j],path{x,x,edge[x].len});137                 for(int y=head[j];y!=-1;y=edge[y].nex)138                     f[0][i][j]=min(f[0][i][j],path{x,y^1,dis[x][y^1]});139             }140             for(int x=head[i];x!=-1;x=edge[x].nex){141                 if ((edge[x].to==j)&&(x!=f[0][i][j].y))f[1][i][j]=min(f[1][i][j],path{x,x,edge[x].len});142                 for(int y=head[j];y!=-1;y=edge[y].nex)143                     if ((y^f[0][i][j].y)!=1)f[1][i][j]=min(f[1][i][j],path{x,y^1,dis[x][y^1]});144             }145             for(int x=head[i];x!=-1;x=edge[x].nex){146                 if ((edge[x].to==j)&&(x!=f[0][i][j].y)&&(x!=f[1][i][j].x))f[2][i][j]=min(f[2][i][j],path{x,x,edge[x].len});147                 for(int y=head[j];y!=-1;y=edge[y].nex)148                     if (((y^f[0][i][j].y)!=1)&&(x!=f[1][i][j].x))f[2][i][j]=min(f[2][i][j],path{x,y^1,dis[x][y^1]});149             }150             f[3][j][i]=path{f[1][i][j].y^1,f[1][i][j].x^1,f[1][i][j].d};151             f[4][j][i]=path{f[2][i][j].y^1,f[2][i][j].x^1,f[2][i][j].d};152         }153     for(int i=1;i<=l;i  ){154         scanf("%d",&x);155         update(1,1,l,i,x);156     }157     for(int i=1;i<=t;i  ){158         scanf("%d%d",&x,&y);159         update(1,1,l,x,y);160         ans=oo;161         for(int j=0;j<5;j  )162             for(int k=0;k<5;k  )ans=min(ans,tr[1].a[j][k]);163         if (ans>=oo)ans=-1;164         printf("%lld\n",ans);165     }166 }

View Code

来源:https://www.icode9.com/content-4-819301.html

(0)

相关推荐