#include <bits/stdc++.h>
using namespace std;
constexpr size_t N = 250000;
vector<unsigned> g[N], t[N];
unsigned l[N], resid[N], c[N];
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
size_t n, m;
cin >> n >> m;
for (size_t i = 0; i < m; ++i)
{
unsigned u, v;
cin >> u >> v;
g[u - 1].push_back(v - 1);
g[v - 1].push_back(u - 1);
}
size_t k;
cin >> k;
for (size_t i = 0; i < k; ++i)
{
size_t L;
cin >> L;
for (size_t j = 0; j < L; ++j)
{
unsigned u;
cin >> u;
l[u - 1] = L;
resid[u - 1] = j;
t[u - 1].resize(L);
c[u - 1] = i;
}
}
for (size_t i = 0; i < n; ++i)
{
if (t[i].empty())
t[i].resize(1);
fill(t[i].begin(), t[i].end(), UINT_MAX);
}
priority_queue<pair<unsigned, unsigned>, vector<pair<unsigned, unsigned>>,
greater<pair<unsigned, unsigned>>>
q;
q.emplace(0, 0);
t[0][0] = 0;
while (!q.empty())
{
auto [d, u] = q.top();
q.pop();
if (d != t[u][l[u] ? d % l[u] : 0])
continue;
if (u == n - 1)
{
cout << d << '\n';
return 0;
}
if (!l[u])
{
for (unsigned const &w : g[u])
if (!l[w])
{
if (d + 1 < t[w][0])
{
t[w][0] = d + 1;
q.emplace(d + 1, w);
}
}
else
{
if ((d + 1) % l[w] != resid[w] && d + 1 < t[w][(d + 1) % l[w]])
{
t[w][(d + 1) % l[w]] = d + 1;
q.emplace(d + 1, w);
}
unsigned const x = d + (resid[w] - (d % l[w]) + l[w]) % l[w];
if (x + 1 < t[w][(x + 1) % l[w]])
{
t[w][(x + 1) % l[w]] = x + 1;
q.emplace(x + 1, w);
}
}
}
else
{
for (auto it = g[u].begin(); it != g[u].end();)
{
unsigned &w = *it;
if (!l[w])
{
if (d + 1 < t[w][0])
{
t[w][0] = d + 1;
q.emplace(d + 1, w);
}
++it;
}
else
{
unsigned x = d + (resid[w] - d % l[w] + l[w]) % l[w];
if (x % l[u] != resid[u])
{
if ((d + 1) % l[w] != resid[w] &&
(c[u] != c[w] || resid[u] != ((resid[w] + 1) % l[u]) || (d % l[w]) != resid[w]) &&
d + 1 < t[w][(d + 1) % l[w]])
{
t[w][(d + 1) % l[w]] = d + 1;
q.emplace(d + 1, w);
}
if (c[w] != c[u] && x + 1 < t[w][(x + 1) % l[w]])
{
t[w][(x + 1) % l[w]] = x + 1;
q.emplace(x + 1, w);
}
size_t i = it - g[u].begin();
swap(w, g[u].back());
g[u].pop_back();
it = g[u].begin() + i;
}
else
{
if ((d + 1) % l[w] != resid[w] &&
(c[u] != c[w] || resid[u] != (resid[w] + 1) % l[u] || d % l[w] != resid[w]) &&
d + 1 < t[w][(d + 1) % l[w]])
{
t[w][(d + 1) % l[w]] = d + 1;
q.emplace(d + 1, w);
}
d += l[u];
if ((d + 1) % l[w] != resid[w] &&
(c[u] != c[w] || resid[u] != (resid[w] + 1) % l[u] || d % l[w] != resid[w]) &&
d + 1 < t[w][(d + 1) % l[w]])
{
t[w][(d + 1) % l[w]] = d + 1;
q.emplace(d + 1, w);
}
x = d + (resid[w] - d % l[w] + l[w]) % l[w];
if (x % l[u] != resid[u] && c[w] != c[u] && x + 1 < t[w][(x + 1) % l[w]])
{
t[w][(x + 1) % l[w]] = x + 1;
q.emplace(x + 1, w);
}
++it;
}
}
}
if ((d + 1) % l[u] != resid[u] && d + 1 < t[u][(d + 1) % l[u]])
{
t[u][(d + 1) % l[u]] = d + 1;
q.emplace(d + 1, u);
}
}
}
cout << "impossible\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
13012 KB |
Output is correct |
| 2 |
Incorrect |
92 ms |
19092 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
13012 KB |
Output is correct |
| 2 |
Incorrect |
97 ms |
19176 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
13012 KB |
Output is correct |
| 2 |
Incorrect |
97 ms |
19176 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
13012 KB |
Output is correct |
| 2 |
Incorrect |
97 ms |
19176 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
13012 KB |
Output is correct |
| 2 |
Incorrect |
92 ms |
19092 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
13012 KB |
Output is correct |
| 2 |
Incorrect |
92 ms |
19092 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
13012 KB |
Output is correct |
| 2 |
Incorrect |
92 ms |
19092 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
