#include <algorithm> #include <cstdio> #include <iostream> #include <queue> #include <vector> using namespace std; // typedef pair<int, int> pii; const int N_MAX = 500+10; const int M_MAX = 1000+10; const int TRIES = 5; int n, m; int l[N_MAX]; vector<int> h[N_MAX]; int S[M_MAX]; int first[N_MAX]; int kmp_T[M_MAX]; void calc_kmp_T() { for (int i = 0; i <= m; i++) kmp_T[i] = -1; for (int i = 1; i <= m; i++) { int pos = kmp_T[i-1]; while((pos != -1) && (S[pos] != S[i-1])) pos = kmp_T[pos]; kmp_T[i] = pos+1; } } void calc_first() { for (int i = 1; i <= n; i++) first[i] = -1; first[1] = 1; queue<int> q; q.push(1); while (!q.empty()) { auto s = q.front(); q.pop(); for (auto z : h[s]) { if (first[z] == -1) { first[z] = first[s] + 1; q.push(z); } } } // cerr << "first["; // for (int i = 1; i <= n; i++) cerr << first[i] << ' '; // cerr << "]\n"; } void build_next(vector<int>& W) { vector<int> nW; for (auto x : W) { for (auto y : h[x]) nW.push_back(y); } swap(W, nW); } bool search_kmp(vector<int>& W) { int sp = 0, kp = 0; while (sp < W.size()) { while ((kp != -1) && (kp == m || S[kp] != W[sp])) kp = kmp_T[kp]; kp++; sp++; if (kp == m) return true; } return false; } int build_search(int k) { if (first[k] == -1) return -1; // cerr << "build_search " << k << '\n'; vector<int> W; W.push_back(k); int d = first[k]; // cerr << "d: " << d << '\n'; while (W.size() < m) { build_next(W); d++; } // cerr << "d: " << d << '\n'; for (int t = 0; t < TRIES; t++) { // cerr << "d=" << d << '\n'; // cerr << "W=["; // for (auto x : W) cerr << x << " "; // cerr << "]\n"; if (search_kmp(W)) return d; build_next(W); d++; } // cerr << "d: " << d << '\n'; return -1; } int main() { scanf("%d %d", &n, &m); for (int i = 1; i <= n; i++) { scanf("%d", l+i); for (int j = 0; j < l[i]; j++) { int hij; scanf("%d", &hij); h[i].push_back(hij); } } for (int i = 0; i < m; i++) { scanf("%d", S+i); } calc_kmp_T(); calc_first(); int ans = -1; for (int i = 1; i <= n; i++) { // cerr << "cell: " << i << '\n'; int res = build_search(i); // cerr << "res: " << res << '\n'; if (ans == -1) ans = res; else ans = (res == -1) ? ans : min(ans, res); } printf("%d\n", ans); return 0; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 | #include <algorithm> #include <cstdio> #include <iostream> #include <queue> #include <vector> using namespace std; // typedef pair<int, int> pii; const int N_MAX = 500+10; const int M_MAX = 1000+10; const int TRIES = 5; int n, m; int l[N_MAX]; vector<int> h[N_MAX]; int S[M_MAX]; int first[N_MAX]; int kmp_T[M_MAX]; void calc_kmp_T() { for (int i = 0; i <= m; i++) kmp_T[i] = -1; for (int i = 1; i <= m; i++) { int pos = kmp_T[i-1]; while((pos != -1) && (S[pos] != S[i-1])) pos = kmp_T[pos]; kmp_T[i] = pos+1; } } void calc_first() { for (int i = 1; i <= n; i++) first[i] = -1; first[1] = 1; queue<int> q; q.push(1); while (!q.empty()) { auto s = q.front(); q.pop(); for (auto z : h[s]) { if (first[z] == -1) { first[z] = first[s] + 1; q.push(z); } } } // cerr << "first["; // for (int i = 1; i <= n; i++) cerr << first[i] << ' '; // cerr << "]\n"; } void build_next(vector<int>& W) { vector<int> nW; for (auto x : W) { for (auto y : h[x]) nW.push_back(y); } swap(W, nW); } bool search_kmp(vector<int>& W) { int sp = 0, kp = 0; while (sp < W.size()) { while ((kp != -1) && (kp == m || S[kp] != W[sp])) kp = kmp_T[kp]; kp++; sp++; if (kp == m) return true; } return false; } int build_search(int k) { if (first[k] == -1) return -1; // cerr << "build_search " << k << '\n'; vector<int> W; W.push_back(k); int d = first[k]; // cerr << "d: " << d << '\n'; while (W.size() < m) { build_next(W); d++; } // cerr << "d: " << d << '\n'; for (int t = 0; t < TRIES; t++) { // cerr << "d=" << d << '\n'; // cerr << "W=["; // for (auto x : W) cerr << x << " "; // cerr << "]\n"; if (search_kmp(W)) return d; build_next(W); d++; } // cerr << "d: " << d << '\n'; return -1; } int main() { scanf("%d %d", &n, &m); for (int i = 1; i <= n; i++) { scanf("%d", l+i); for (int j = 0; j < l[i]; j++) { int hij; scanf("%d", &hij); h[i].push_back(hij); } } for (int i = 0; i < m; i++) { scanf("%d", S+i); } calc_kmp_T(); calc_first(); int ans = -1; for (int i = 1; i <= n; i++) { // cerr << "cell: " << i << '\n'; int res = build_search(i); // cerr << "res: " << res << '\n'; if (ans == -1) ans = res; else ans = (res == -1) ? ans : min(ans, res); } printf("%d\n", ans); return 0; } |