#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops)
#include <bits/stdc++.h>
using namespace std ;
const int inf = 1e9 ;
const int MAX = 3e5 + 10 ;
const int K = 30 ;
int arr[MAX] ;
int n , m , k ;
vector< vector<int> >adj(MAX) ;
vector<int>v[MAX] ;
int watch[MAX] , cycle_sz[MAX] , id[MAX] ;
int dist[MAX][K] ;
int calc[MAX][205] ;
bool check(int node , int child , int tim)
{
assert(watch[child] != 0) ;
int x = watch[node] ;
int tim_node = 2e9 ;
if(watch[node])
{
int cur = tim % cycle_sz[x] ;
tim_node = tim + (id[node] - cur + cycle_sz[x]) % cycle_sz[x] ;
}
int tim_child = -2e9 ;
x = watch[child] ;
int cur = tim % cycle_sz[x] ;
tim_child = tim + (id[child] - cur + cycle_sz[x]) % cycle_sz[x] ;
return (tim_child < tim_node-1 || (tim_child == tim_node - 1 && watch[child] != watch[node])) ;
}
void solve(int src)
{
for(int i = 1 ; i <= n ; ++i)
dist[i][0] = dist[i][1] = inf ;
priority_queue< array<int , 3> , vector< array<int , 3> > , greater< array<int , 3> > >q ;
dist[src][0] = 0 ;
q.push({0 , src , 0}) ;
while(!q.empty())
{
array<int , 3>a = q.top() ;
q.pop() ;
int node = a[1] , cost = a[0] , t = a[2] ;
if(dist[node][t] < cost)
continue ;
for(auto &child : adj[node])
{
int child2 = child ;
int cost2 = cost + 1 ;
if((!watch[child2]))
{
if(cost2 < dist[child2][0])
{
dist[child2][0] = cost2 ;
q.push({cost2 , child2 , 0}) ;
}
continue ;
}
int x = watch[child2] ;
if(check(node , child2 , cost)) //handle waiting for some time
{
int cur = cost % cycle_sz[x] ;
cost2 = cost + (id[child2] - cur + cycle_sz[x]) % cycle_sz[x] + 1 ;
if(cost2 < dist[child2][1])
{
dist[child2][1] = cost2 ;
q.push({cost2 , child2 , 1}) ;
}
}
cost2 = cost + 1 ;
//handle corridor
if(v[x][(cost2 - 1) % cycle_sz[x]] == child2 && v[x][cost2 % cycle_sz[x]] == node)
continue ;
if(v[x][cost2 % cycle_sz[x]] != child2) //go without waiting
{
if(cost2 < dist[child2][t])
{
dist[child2][t] = cost2 ;
q.push({cost2 , child2 , t}) ;
}
}
}
}
}
void solve2(int src)
{
for(int i = 1 ; i <= n ; ++i)
{
for(int j = 0 ; j < K ; ++j)
dist[i][j] = inf ;
}
queue< pair<int , int> >q ;
dist[src][0] = 0 ;
q.push({src , 0}) ;
while(!q.empty())
{
pair<int , int>p = q.front() ;
q.pop() ;
int node = p.first , wait = p.second ;
int cost = dist[node][wait] , x = watch[node] ;
if(node == n)
return ;
if((!x) || (v[x][calc[cost + 1][cycle_sz[x]]] != node))
{
if(wait+1 < K && dist[node][wait+1] == inf)
{
dist[node][wait+1] = cost + 1 ;
q.push({node , wait+1}) ;
}
}
for(auto &child : adj[node])
{
int child2 = child ;
int cost2 = cost + 1 ;
x = watch[child] ;
if(x > 0 && v[x][calc[cost2 - 1][cycle_sz[x]]] == child2 && v[x][calc[cost2][cycle_sz[x]]] == node)
continue ;
if(x > 0 && v[x][calc[cost2][cycle_sz[x]]] == child2)
continue ;
if(dist[child2][wait] == inf)
{
dist[child2][wait] = cost2 ;
q.push({child2 , wait}) ;
}
}
}
}
int main()
{
ios_base::sync_with_stdio(0) ;
cin.tie(0) ;
cin>>n>>m ;
for(int i = 0 ; i < m ; ++i)
{
int x , y ;
cin>>x>>y ;
adj[x].push_back(y) ;
adj[y].push_back(x) ;
}
cin>>k ;
for(int i = 1 ; i <= k ; ++i)
{
cin>>cycle_sz[i] ;
v[i].resize(cycle_sz[i]) ;
for(int j = 0 ; j < cycle_sz[i] ; ++j)
{
cin>>v[i][j] ;
watch[v[i][j]] = i ;
id[v[i][j]] = j ;
}
}
bool flag = true ;
for(int i = 1 ; i <= n ; ++i)
{
for(auto &child : adj[i])
flag &= (watch[i] == 0 || watch[child] == 0 || watch[i] == watch[child]) ;
}
if(flag) //no corridor connects two two different routes
{
solve(1) ;
if(dist[n][0] == inf)
cout<<"impossible\n" ;
else
cout<<dist[n][0]<<"\n" ;
}
else
{
for(int j = 1 ; j < 205 ; ++j)
{
calc[0][j] = 0 ;
for(int i = 1 ; i < n + 1000 ; ++i)
{
calc[i][j] = calc[i-1][j] + 1 ;
if(calc[i][j] == j)
calc[i][j] = 0 ;
}
}
solve2(1) ;
int ans = inf ;
for(int i = 0 ; i < K ; ++i)
ans = min(ans , dist[n][i]) ;
if(ans == inf)
cout<<"impossible\n" ;
else
cout<<ans<<"\n" ;
}
return 0 ;
}
Compilation message
watchmen.cpp:2:22: warning: missing terminating " character
2 | #pragma GCC optimize("unroll-loops)
| ^
watchmen.cpp:2:22: error: missing terminating " character
2 | #pragma GCC optimize("unroll-loops)
| ^~~~~~~~~~~~~~
watchmen.cpp:2:21: warning: '#pragma GCC optimize' is not a string or number [-Wpragmas]
2 | #pragma GCC optimize("unroll-loops)
| ^
