#include <bits/stdc++.h>
#define ll long long
#define ar array
#define db double
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define rint(l, r) uniform_int_distribution<int>(l, r)(rng)
template<typename T> bool ckmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
void test_case() {
int n, m;
cin >> n >> m;
vector<vector<int>> adj(n+1);
for (int i = 0; i < m; i++) {
int x, y;
cin >> x >> y;
adj[x].push_back(y);
adj[y].push_back(x);
}
vector<int> size(n+1, 1), who(n+1, -1), id(n+1, -1);
int Q; cin >> Q;
for (int i = 0; i < Q; i++) {
int cur; cin >> cur;
for (int j = 0; j < cur; j++) {
int x; cin >> x;
size[x] = cur;
who[x] = j;
id[x] = i;
}
}
// if size[v]
// then, dist[v] % size[v] != who[v]
vector<vector<int>> dist(n+1);
for (int i = 1; i <= n; i++) {
dist[i].resize(size[i], 1e9);
}
// number of nodes = N + sum(L)
const int N = 1501; // max edge length = 1500
vector<vector<ar<int, 3>>> queues(N);
queues[0].push_back({1, 0, 1});
dist[1][0] = 0;
int max_dist = 0;
for (int cost = 0; cost <= max_dist; cost++) {
int use = cost % N;
while (queues[use].size()) {
auto [v, time, len] = queues[use].back(); queues[use].pop_back();
if (dist[v][time] == cost) {
for (int u : adj[v]) {
// cost + i - 1 = who[u] (mod size[u])
// [cost, cost + i - 1] mod size[u] != who[u]
int res;
if (size[v] > 1) {
if (cost % size[v] < who[v]) {
res = who[v] - cost % size[v];
}
else {
res = who[v] + (size[v] - cost % size[v]);
}
}
else res = 1e9;
ar<int, 2> avoid{int(1e9), int(1e9)};
// (cost + i) % size[u] == who[u]
avoid[0] = ~who[u] ? ((who[u] - cost) % size[u] + size[u]) % size[u] : 1e9;
if (id[u] == id[v] && ((who[u] + 1) % size[u] == who[v]) && ~who[u]) {
// (cost + i - 1) = who[u] (mod size[u])
avoid[1] = ((who[u] + 1 - cost) % size[u] + size[u]) % size[u];
}
if (avoid[0] > avoid[1]) swap(avoid[0], avoid[1]);
auto add = [&](int L, int R) {
if (ckmin(dist[u][(cost+L)%size[u]], cost + L)) {
queues[(cost + L) % N].push_back({u, (cost + L) % size[u], R-L+1});
ckmax(max_dist, cost + R);
}
};
int to = min(res, size[u]);
if (avoid[0] == 1e9) {
add(1, to);
}
else {
if (1 < avoid[0]) {
add(1, avoid[0] - 1);
}
if (avoid[1] > to) {
if (avoid[0] + 1 <= to) add(avoid[0] + 1, to);
}
else {
if (avoid[0] + 1 < avoid[1]) add(avoid[0] + 1, avoid[1] - 1);
if (avoid[1] + 1 <= to) add(avoid[1] + 1, to);
}
}
/*
for (int i = 1; i <= to; i++) if (i != avoid[0] && i != avoid[1]) {
if (ckmin(dist[u][(cost+i)%size[u]], cost + i)) {
queues[(cost + i) % N].push_back({u, (cost + i) % size[u], 1});
ckmax(max_dist, cost + i);
}
}
*/
}
}
if (len > 1) {
if (ckmin(dist[v][(cost+1)%size[v]], cost + 1))
queues[(cost + 1) % N].push_back({v, cost + 1, len - 1});
}
}
}
int ans = *min_element(all(dist[n]));
if (ans == 1e9) {
cout << "impossible\n";
return;
}
cout << ans << '\n';
}
int main() {
cin.tie(0)->sync_with_stdio(0);
int t = 1;
// cin >> t;
while (t--) test_case();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
97 ms |
1464 KB |
Output is correct |
| 2 |
Runtime error |
42 ms |
25340 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
98 ms |
1508 KB |
Output is correct |
| 2 |
Runtime error |
43 ms |
25536 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
98 ms |
1508 KB |
Output is correct |
| 2 |
Runtime error |
43 ms |
25536 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
98 ms |
1508 KB |
Output is correct |
| 2 |
Runtime error |
43 ms |
25536 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
97 ms |
1464 KB |
Output is correct |
| 2 |
Runtime error |
42 ms |
25340 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
97 ms |
1464 KB |
Output is correct |
| 2 |
Runtime error |
42 ms |
25340 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
97 ms |
1464 KB |
Output is correct |
| 2 |
Runtime error |
42 ms |
25340 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
