记$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}<d_{y,t}$，即可以使用dijkstra实现，时间复杂度为$o(M\log M)$，需要进行优化

 

具体的，将转移分为四类，分别进行优化：

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<bits/stdc++.h>
  2 using namespace std;
  3 #define N 250005
  4 #define M 5000005
  5 struct Edge{
  6     int pre,nex,fr,to;
  7 }edge[M<<1];
  8 struct Data{
  9     int x,s,d;
 10     bool operator < (const Data &k)const{
 11         return d>k.d;
 12     }
 13 };
 14 priority_queue<Data>q;
 15 int n,m,t,E,x,y,ans,head[N],l[N],bl[N],pos[N],suml[N],vis0[N],vis[M],d[M];
 16 int read(){
 17     int x=0;
 18     char c=getchar();
 19     while ((c<'0')||(c>'9'))c=getchar();
 20     while ((c>='0')&&(c<='9')){
 21         x=x*10+c-'0';
 22         c=getchar();
 23     }
 24     return x;
 25 }
 26 int id(int x,int s){
 27     return suml[x-1]+s+1;
 28 }
 29 void upd(int x,int D){
 30     int s=D%l[x];
 31     if (d[id(x,s)]>D){
 32         d[id(x,s)]=D;
 33         q.push(Data{x,s,d[id(x,s)]});
 34     }
 35 }
 36 int get_nex(int d,int l,int s){
 37     if (d%l>s)d+=l-d%l;
 38     if (d%l<s)d+=s-d%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<x;j++){
103             y=read();
104             l[y]=x,bl[y]=i,pos[y]=j;
105         }
106     }
107     for(int i=1;i<=n;i++)suml[i]=suml[i-1]+l[i];
108     ans=calc();
109     if (ans!=0x3f3f3f3f)printf("%d\n",ans);
110     else printf("impossible\n");
111     return 0;
112 }

View Code