// pana la ora 1
bool home = 1;
bool verbose = 1;
#include <iostream>
#include <cstdio>
#include <vector>
#include <cassert>
#include <queue>
using namespace std;
struct T {
int v;
int r;
};
const int N = 250000 + 7;
const int V = (int)1e6 + 7;
const int INF = (int)1e9 + 7;
int n;
int m;
int cnt_cycles;
int suml;
vector<pair<int, int>> edges;
vector<int> cycles[N];
int cycle_id[N];
int cycle_location[N];
int single_vertex_id[N];
vector<int> cycle_vertex_id[N];
int dp[V];
T what[V];
int y;
vector<int> g[N];
priority_queue<pair<int, int>> pq;
void relax(int id, int d) {
assert(1 <= id && id <= y);
if (d < dp[id]) {
dp[id] = d;
pq.push({ -dp[id], id });
}
}
int main() {
if (!home) {
verbose = 0;
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
if (home) {
verbose = 1;
FILE* stream;
freopen_s(&stream, "input.txt", "r", stdin);
}
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int a, b;
cin >> a >> b;
g[a].push_back(b);
g[b].push_back(a);
edges.push_back({ a, b });
}
cin >> cnt_cycles;
for (int i = 1; i <= cnt_cycles; i++) {
int l;
cin >> l;
suml += l;
cycles[i].resize(l);
for (int j = 0; j < (int)cycles[i].size(); j++) {
cin >> cycles[i][j];
assert(cycle_id[cycles[i][j]] == 0);
cycle_id[cycles[i][j]] = i;
cycle_location[cycles[i][j]] = j;
}
if (verbose) {
cout << " ---> ";
for (auto& v : cycles[i]) {
cout << v << " ";
}
cout << "\n";
}
}
for (int a = 1; a <= n; a++) {
if (cycle_id[a] == 0) {
y++;
single_vertex_id[a] = y;
what[y] = { a, 0 };
}
else {
int id = cycle_id[a];
cycle_vertex_id[a].resize((int) cycles[id].size());
for (int j = 0; j < (int)cycles[id].size(); j++) {
y++;
cycle_vertex_id[a][j] = y;
what[y] = { a, j };
}
}
}
for (int i = 1; i <= y; i++) {
dp[i] = INF;
}
if (verbose) {
cout << "################################################################################### \n";
}
assert(cycle_id[1] == 0);
assert(cycle_id[n] == 0);
dp[single_vertex_id[1]] = 0;
pq.push({ 0, single_vertex_id[1] });
while (!pq.empty()) {
int d = -pq.top().first;
int idv = pq.top().second;
pq.pop();
if (dp[idv] != d) {
continue;
}
int vertex = what[idv].v;
int r = what[idv].r;
if (cycle_id[vertex] == 0) {
assert(r == 0);
for (auto& vecin : g[vertex]) {
if (cycle_id[vecin] == 0) {
// vecin is a single vertex
relax(single_vertex_id[vecin], d + 1);
}
else {
// vecin is on a cycle
int cycle_vecin = cycle_id[vecin];
int l_vecin = cycles[cycle_vecin].size();
for (int twait = 0; twait < l_vecin; twait++) {
// la momentul d + 1 + twait
if ((d + 1 + twait) % l_vecin == cycle_location[vecin]) {
continue;
}
relax(cycle_vertex_id[vecin][(d + 1 + twait) % l_vecin], d + 1 + twait);
}
}
}
}
else {
int cycle = cycle_id[vertex];
int l = cycles[cycle].size();
/*
wait a moment here
*/
if ((d + 1) % l != cycle_location[vertex]) {
relax(cycle_vertex_id[vertex][(d + 1) % l], d + 1);
}
/*
don't wait a moment here
*/
assert(0 <= r && r < l);
assert(d % l == r);
for (auto& vecin : g[vertex]) {
if (cycle_id[vecin] == 0) {
// vecin is a single vertex
relax(single_vertex_id[vecin], d + 1);
}
else {
// vecin is on a cycle
int cycle_vecin = cycle_id[vecin];
int l_vecin = cycles[cycle_vecin].size();
if (cycle_vecin == cycle) {
// vecin is on the same cycle
if ((d + 1) % l_vecin == cycle_location[vecin]) {
continue;
}
if (d % l_vecin == cycle_location[vecin] && (d + 1) % l_vecin == cycle_location[vertex]) {
continue;
}
relax(cycle_vertex_id[vecin][(d + 1) % l_vecin], d + 1);
/*
vertex -> vecin <- vecin2
*/
}
else {
// vecin is on a different cycle
if ((d + 1) % l_vecin == cycle_location[vecin]) {
continue;
}
relax(cycle_vertex_id[vecin][(d + 1) % l_vecin], d + 1);
}
}
}
}
}
int sol = dp[single_vertex_id[n]];
if (sol == INF) {
cout << "impossible\n";
return 0;
}
cout << sol << "\n";
return 0;
/*for (auto& edge : edges) {
int a = edge.first, b = edge.second;
if (cycle_id[a] == 0 && cycle_id[b] == 0) {
// just a normal edge
addEdge(single_vertex_id[a], single_vertex_id[b], 1);
continue;
}
if (cycle_id[a] != 0 && cycle_id[b] == 0) {
swap(a, b);
}
if (cycle_id[a] == 0 && cycle_id[b] != 0) {
continue;
}
assert(cycle_id[a] != 0 && cycle_id[b] != 0);
}*/
return 0;
}
Compilation message
watchmen.cpp: In function 'int main()':
watchmen.cpp:57:5: error: 'freopen_s' was not declared in this scope; did you mean 'freopen64'?
57 | freopen_s(&stream, "input.txt", "r", stdin);
| ^~~~~~~~~
| freopen64
