이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math,inline")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,lzcnt,mmx,abm,avx,avx2,fma")
#include <bits/stdc++.h>
using namespace std;
#define tp3 tuple<int, int, int>
const int N = 1e5 + 1, K = 2750 + 1, inf = INT_MAX;
int n, m, k, Lcm, copId[N];
vector<int> adj[N], cop[N];
vector<vector<int>> dp;
signed main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
memset(copId, -1, sizeof(copId));
cin >> n >> m;
for (int i = 0; i < m; i++) {
int x, y;
cin >> x >> y;
x--; y--;
adj[x].push_back(y);
adj[y].push_back(x);
}
for (int i = 0; i < n; i++) {
adj[i].push_back(i);
}
cin >> k;
Lcm = 1;
for (int i = 0; i < k; i++) {
int x;
cin >> x;
Lcm = min(n + K, lcm(Lcm, x));
cop[i].resize(x);
for (int& j : cop[i]) {
cin >> j;
j--;
copId[j] = i;
}
}
dp.resize(Lcm, vector<int>(n, inf));
queue<tp3> q;
q.push(make_tuple(0, 0, 0)); // {dis, sec, node}
while (!q.empty()) {
int d = get<0>(q.front());
int s = get<1>(q.front());
int u = get<2>(q.front());
q.pop();
if (copId[u] != -1) {
int x = copId[u];
if (cop[x][s % cop[x].size()] == u) continue;
}
if (dp[s][u] <= d) continue;
dp[s][u] = d;
for (int& v : adj[u]) {
int nwSec = (s+1) % Lcm;
if (copId[v] != -1) {
int x = copId[v];
if (cop[x][s] == v && cop[x][(s+1) % cop[x].size()] == u) {
// no puedo ir a este nodo
}
else {
if (dp[nwSec][v] > d+1) q.push(make_tuple(d+1, nwSec, v));
}
}
else {
if (dp[nwSec][v] > d+1) q.push(make_tuple(d+1, nwSec, v));
}
}
}
int ans = inf;
for (int i = 0; i < Lcm; i++) {
ans = min(ans, dp[i][n-1]);
}
if (ans == inf) cout << "impossible\n";
else cout << ans << "\n";
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |