[loj2842]野猪
2024-08-29 23:24:52
首先，并不一定走“除了上一次来的边”以外的最短路，但考虑“除了上一次来的边”以外的最短路和次短路（这里的次短路指最后一条边与最短路不同的“最短路”），必然是走这两者之一
（”除了上一次来的边“指第一步不走上一次来的边）
证明很显然，因为如果最短路不好必然是因为下一次需要先走最短路那条边，那么这次走次短路即可
但由于我们所预处理的并不能与实际的$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 }
最新文章
- linux作业
- WCF服务创建与抛出强类型SOAP Fault
- 栈的理解以及如何计算程序所需栈的大小并在IAR中设置栈
- 记录js学习之this用法
- 使用miniui框架制作树形节点
- andriod终端操作命令
- android定位GPS定位 代码实现
- 【WEB小工具】jQuery函数
- ERP 实施和应用不成功共同点
- 【转】Android 避免APP启动闪黑屏(Theme和Style)
- spdlog源码阅读 (1): sinks
- [Code] 递归函数在函数式 Java 中的实现
- UNIX网络编程——揭开网络编程常见API的面纱【上】
- selenium+谷歌无头浏览器爬取网易新闻国内板块
- Vue对变量的监控
- PythonStudy——编程基础 Python Primary
- Hadoop记录-hadoop介绍
- NIO 中的读和写
- sass嵌套风格
- Delphi 资源管理器套件