#include <bits/stdc++.h>
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
using namespace std;
typedef long long lint;
typedef pair<lint, lint> pi;
const int mod = 1e9 + 7;
const int MAXN = 250005;
vector<lint> dist[MAXN];
vector<int> gph[MAXN];
struct node{
int x, y; lint dist;
bool operator<(const node &n)const{
return dist > n.dist;
}
};
void solve(int n, vector<pi> edg, vector<int> v, int s, int e){
for(auto &[u, v] : edg){
gph[u].push_back(v);
gph[v].push_back(u);
}
int p = 0;
vector<pi> cycs;
for(int i = 0; i < sz(v); i++){
for(int j = 0; j < v[i]; j++){
dist[p].resize(v[i], 1e18);
p++;
cycs.emplace_back(i, j);
}
}
while(p < n){
dist[p++].resize(1, 1e18);
cycs.emplace_back(-1, 0);
}
priority_queue<node> pq;
auto enq = [&](int v, lint d){
if(sz(dist[v]) > 1 && d % sz(dist[v]) == cycs[v].second) return;
if(dist[v][d % sz(dist[v])] > d){
dist[v][d % sz(dist[v])] = d;
pq.push({v, (int)(d % sz(dist[v])), d});
}
};
enq(s, 0);
vector<int> visCount(n);
while(sz(pq)){
auto x = pq.top(); pq.pop();
int v = x.x;
if(dist[v][x.y] != x.dist) continue;
enq(v, x.dist + 1);
if(sz(dist[v]) > 1){
int i1 = v - 1;
int i2 = v + 1;
if(cycs[v].second == 0) i1 += sz(dist[v]);
if(cycs[v].second == sz(dist[v]) - 1) i2 -= sz(dist[v]);
enq(i1, x.dist + 1);
enq(i2, x.dist + 1);
}
if(sz(dist[x.x]) > 1 && visCount[x.x]) continue;
visCount[x.x]++;
for(auto &y : gph[x.x]){
if(cycs[x.x].first >= 0 &&
cycs[x.x].first == cycs[y].first &&
x.dist % sz(dist[x.x]) == cycs[y].second &&
(x.dist + 1) % sz(dist[x.x]) == cycs[x.x].second){
continue;
}
enq(y, x.dist + 1);
if(cycs[x.x].first < 0 || cycs[x.x].first != cycs[y].first){
if(sz(dist[y]) <= 1){
for(int k = 0; k < sz(dist[y]); k++){
enq(y, x.dist + 1 + sz(dist[x.x]) * k);
}
}
else{
enq(y, x.dist + 1);
enq(y, x.dist + 1 + ((cycs[y].second - x.dist) % sz(dist[y]) + sz(dist[y])) % sz(dist[y]));
}
}
}
}
lint ans = *min_element(all(dist[e]));
if(ans < 1e17) cout << ans << "\n";
else cout << "impossible\n";
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n, m; cin >> n >> m;
vector<pi> edg;
for(int i = 0; i < m; i++){
int u, v; cin >> u >> v;
edg.emplace_back(u-1, v-1);
}
vector<int> idx(n, -1);
int cnt = 0;
int k; cin >> k;
vector<int> siz(k);
for(int i = 0; i < k; i++){
cin >> siz[i];
for(int j = 0; j < siz[i]; j++){
int v; cin >> v;
idx[v - 1] = cnt++;
}
}
for(int i = 0; i < n; i++){
if(idx[i] == -1) idx[i] = cnt++;
}
for(auto &[u, v] : edg){
u = idx[u];
v = idx[v];
}
solve(n, edg, siz, idx[0], idx[n - 1]);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
15496 KB |
Output is correct |
| 2 |
Incorrect |
91 ms |
23952 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
15500 KB |
Output is correct |
| 2 |
Incorrect |
73 ms |
23880 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
15500 KB |
Output is correct |
| 2 |
Incorrect |
73 ms |
23880 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
15500 KB |
Output is correct |
| 2 |
Incorrect |
73 ms |
23880 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
15496 KB |
Output is correct |
| 2 |
Incorrect |
91 ms |
23952 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
15496 KB |
Output is correct |
| 2 |
Incorrect |
91 ms |
23952 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
15496 KB |
Output is correct |
| 2 |
Incorrect |
91 ms |
23952 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
