[loj3560]From Hacks to Snitches
记$l_{x}$为经过$x$的守卫路径长度,若不存在此类守卫则定义$l_{x}=1$
注意到若能在时刻$t$到达$x$,显然也能在时刻$t+l_{x}$到达$x$(顺着守卫的方向走),因此定义$d_{x,s}$为最早到达$x$?且$\equiv s(mod\ l_{x})$的时刻,即具备单调性,进而不难得到转移如下——
$$
d_{x,s}\rightarrow
d_{y,t}=\min_{k\in N,d_{x,s}+k\cdot l_{x}+1\equiv t(mod\ l_{y})}(d_{x,s}+k\cdot l_{x}+1)
$$
其中转移需满足:1.$x=y$或$(x,y)\in E$;2.时刻$t$没有守卫经过$y$;3.时刻$t$没有守卫从$y$到$x$(注意$t$与$d_{x,s}+k\cdot l_{x}+1$等价)
在上述状态转移中,总转移数$M=\sum_{(x,y)\in E}l_{x}l_{y}\le mL+L^{4}$(对$x,y$是否均被守卫经过分类讨论),并且转移时有$d_{x,s} 具体的,将转移分为四类,分别进行优化: 1.$y$未被守卫经过,根据dijkstra的单调性,对于每一个$x$仅需要对此类$y$转移一次即可 2.$x$未被守卫经过且$y$被守卫经过,令$T$为$y$在$d_{x,s}$之后最早被守卫经过的时刻,仅转移到$d_{x,s}+1$和$T+1$即可 另外,若$d_{x,s}+1=T$则前者不能转移,正确性注意到其余的部分均会在$y$内部进行转移 3.$(x,y)$是某个守卫经过的边(包括正序和逆序),直接处理即可(注意仅需要转移$k=0$时) 4.除上述情况以外,即$x,y$均被守卫经过且不是某个守卫经过的边 令$T$为$y$在$d_{x,s}$之后最早被守卫经过的时刻,若时刻$T$没有守卫经过$x$,那么就可以在$y$上等待并在时刻$T$返回$x$(之后再返回$y$) 通过此方式,能转移到所有的$d_{y,t}$,并且已经达到下限(注意dijkstra的贪心),因此类似第2种情况转移后,就可以删除该边 进一步的,若时刻$T$有守卫经过$x$,那么对于$T$之前的时刻可以直接转移,否则必须绕若干圈后直至$T$时刻之后 记$T_{1}$为$T$以及$T$之后最早$\equiv s(mod\ l_{x})$的时刻(转到$T_{1}$时停止)$,T_{2}$为$y$在$T_{1}$之后最早被守卫经过的时刻,类似的判定时刻$T_{2}$是否有守卫经过$x$:若没有守卫经过$x$则处理方式与$T$相同(但不删除该边),否则简单分析不难证明走更多圈也无意义 考虑此时的$M$,将转移分为三类,分别进行分析: 1.$x,y$中某个点未被守卫经过,这类边仅会转移1次,因此总转移数为$o(m)$ 2.$(x,y)$是某个守卫经过的边,这类边共$L$条且至多转移$L$次,因此总转移数为$o(L^{2})$ 3.除上述情况外,即优化中的第4种情况,此时考虑$x$向环$y$的总转移数:第一次转移$?_{y}$次后,至多剩下$\lceil\frac{?_{y}}{l_{x}}\rceil$条边,即剩下的$l_{x}-1$个$s$转移次数均仅为$\lceil\frac{?_{y}}{l_{x}}\rceil$,求和后为$?_{y}+(l_{x}-1)\lceil\frac{?_{y}}{l_{x}}\rceil\le 2?_{y}$ 再对$x$所在环上每一个点求和,最终两环之间总转移数即$o(?_{x}?_{y})$,求和后显然即$o(L^{2})$ 综上,总转移数$M$是$o(m+L^{2})$的,而时间复杂度为$o(M\log M)$,可以通过 1 #include
l;
39 return d;
40 }
41 void add(int x,int y){
42 edge[E]=Edge{-1,head[x],x,y};
43 if (head[x]!=-1)edge[head[x]].pre=E;
44 head[x]=E++;
45 }
46 void del(int k){
47 if (edge[k].nex>=0)edge[edge[k].nex].pre=edge[k].pre;
48 if (edge[k].pre<0)head[edge[k].fr]=edge[k].nex;
49 else edge[edge[k].pre].nex=edge[k].nex;
50 }
51 int calc(){
52 memset(d,0x3f,sizeof(d));
53 upd(1,0);
54 while (!q.empty()){
55 int x=q.top().x,s=q.top().s,D=q.top().d;
56 q.pop();
57 if (vis[id(x,s)])continue;
58 vis[id(x,s)]=1;
59 if ((!bl[x])||((s+1)%l[x]!=pos[x]))upd(x,D+1);
60 for(int i=head[x];i!=-1;i=edge[i].nex){
61 int y=edge[i].to,T=get_nex(D+1,l[y],pos[y]);
62 if (!bl[y]){
63 upd(y,D+1),del(i);
64 continue;
65 }
66 if (!bl[x]){
67 if (D+1!=T)upd(y,D+1);
68 upd(y,T+1);
69 continue;
70 }
71 if ((bl[x]==bl[y])&&((pos[x]+1)%l[x]==pos[y])){
72 upd(y,D+1);
73 continue;
74 }
75 if ((bl[x]==bl[y])&&((pos[y]+1)%l[x]==pos[x])){
76 if ((s!=pos[y])&&((s+1)%l[x]!=pos[y]))upd(y,D+1);
77 continue;
78 }
79 if (D+1!=T)upd(y,D+1);
80 if (T%l[x]!=pos[x]){
81 upd(y,T+1),del(i);
82 continue;
83 }
84 int T1=get_nex(T,l[x],s),T2=get_nex(T1+1,l[y],pos[y]);
85 if (T1+1!=T2)upd(y,T1+1);
86 if (T2%l[x]!=pos[x])upd(y,T2+1);
87 }
88 }
89 return d[id(n,0)];
90 }
91 int main(){
92 n=read(),m=read();
93 memset(head,-1,sizeof(head));
94 for(int i=1;i<=m;i++){
95 x=read(),y=read();
96 add(x,y),add(y,x);
97 }
98 t=read();
99 for(int i=1;i<=n;i++)l[i]=1;
100 for(int i=1;i<=t;i++){
101 x=read();
102 for(int j=0;j