不难发现数据范围小到 bfs 和 spfa 都随便跑。

bfs 两个注意点：

• 要用 \(vis\) 判重，如果是普通的 bfs 求最短路，因为状态数少就不必要判重，但是这样可能会无解从而无限扩展。
• \(k\) 可能等于 0 ，在 \(\%k\) 的时候要特判。

如果你用 spfa 的话考虑的就相对多一些。

用 \(d[u][t]\) 表示在 \(t\) 个周期内到达 \(u\) 点的最小时间，可以看出这个状态表示无后效性和最优子结构的。

周期的话直接用一个数组 \(lock[k][u][v]\) 表示在 \(k\) 个周期能否从 \(u\) 到 \(v\)，如果 \(t\) 加了 \(k\) 次还不能到 \(v\) 则这条路封死，应 break 掉。

还有就是都要注意的 \(k\) 等于 0。

#include<bits/stdc++.h>
#define IXcape cout<<endl;return 0
#define Venti cout<<"\nVenti!\n"
using namespace std;
const int V=2e2+10,E=30;
bool del[V][V][V],vis[V][V];
int n,m,k;
vector<int> g[V];
struct node{
    int id,t,cnt;
};

inline
void bfs(void){
    queue<node>q;
    q.push(node{1,0,0});
    vis[1][0]=1;
    bool flag=0;
    while(q.size()){
        node x=q.front();
        q.pop();
        if(x.id==n){
            cout<<x.t<<'\n';
            flag=1;
            break;
        }
        int t=x.t;
        for(int i=0;i<g[x.id].size();i++){
            int y=g[x.id][i];
            if(del[(k?(t%k+1):t+1)][x.id][y]==0){
                if(vis[y][(k?(t%k+1):t+1)]==0){
                    q.push(node{y,t+1,0});
                    vis[y][(k?(t%k+1):t+1)]=1;
                }
            }
        }
        if(vis[x.id][(k?(t%k+1):t+1)]==0){
            q.push(node{x.id,t+1,x.cnt+1});
            vis[x.id][(k?(t%k+1):t+1)]=1;
        }
    }
    if(!flag)
        cout<<"No solution.";
}

signed main(){
    freopen("sand.in","r",stdin);
    freopen("sand.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int x,y;
        cin>>x>>y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    
    cin>>k;
    for(int i=1;i<=k;i++){
        int x,y;
        while(cin>>x>>y){
            if(x==0&&y==0) 
                break;
            del[i][x][y]=del[i][y][x]=1;
        }
    }
    bfs();
    IXcape;
}