#include <iostream> #include <vector> #include <algorithm> #include <set> #include <unordered_set> #include <queue> #include <stack> #include <string> #include <map> #include <unordered_map> #define FOR(i,b,e) for(int i=(b); i <= (e); ++i) #define FORD(i,b,e) for(int i=(b); i >= (e); --i) #define SIZE(c) (int) (c).size() #define FORE(i,c) FOR(i,0,SIZE(c)-1) #define FORDE(i,c) FORD(i,SIZE(c)-1,0) #define MIN(x,y) ( ((x) < (y))? (x) : (y) ) #define MAX(x,y) ( ((x) > (y))? (x) : (y) ) #define PB push_back #define MP make_pair #define ST first #define ND second #define INF 1000000001 using namespace std; typedef long long int LLI; typedef pair < int , int > PII; typedef pair < LLI , LLI > PLL; typedef vector < int > VI; typedef vector < bool > VB; typedef vector < PII > VP; typedef vector < LLI > VL; typedef vector < PLL > VPL; typedef vector < VI > VVI; typedef vector < VL > VVL; typedef vector < VB > VVB; typedef VVI Matrix; Matrix zero(int n, int m) { Matrix ans(n); FORE(i,ans) ans[i].resize(m,0); return ans; } Matrix identity(int n) { Matrix ans = zero(n, n); FOR(i,0,n-1) ans[i][i] = 1; return ans; } Matrix operator *(const Matrix &a, const Matrix &b) { int n = SIZE(a), k = SIZE(a[0]), m = SIZE(b[0]); Matrix ans = zero(n, m); FOR(i,0,n-1) FOR(j,0,k-1) FOR(t,0,m-1) ans[i][t] = min(1, ans[i][t] + a[i][j] * b[j][t]); return ans; } /*************************************************************************/ int main() { ios_base::sync_with_stdio(0); int n, b, r; cin >> n >> b >> r; Matrix M(n); FOR(i,0,n-1) FOR(j,0,n-1) { char b; cin >> b; M[i].PB(b - '0'); } VB robot(n,0); while (r--) { int x; cin >> x; x--; robot[x] = 1; } Matrix C = identity(n); int maxOp = (100 * 1000 * 1000) / (n * n * n); FOR(i,0,maxOp) { bool good = 1; FOR(rob,0,n-1) if (robot[rob]) FOR(j,b,n-1) if (C[rob][j]) good = 0; if (good) { cout << i; return 0; } C = C * M; } cout << -1; 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 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 | #include <iostream> #include <vector> #include <algorithm> #include <set> #include <unordered_set> #include <queue> #include <stack> #include <string> #include <map> #include <unordered_map> #define FOR(i,b,e) for(int i=(b); i <= (e); ++i) #define FORD(i,b,e) for(int i=(b); i >= (e); --i) #define SIZE(c) (int) (c).size() #define FORE(i,c) FOR(i,0,SIZE(c)-1) #define FORDE(i,c) FORD(i,SIZE(c)-1,0) #define MIN(x,y) ( ((x) < (y))? (x) : (y) ) #define MAX(x,y) ( ((x) > (y))? (x) : (y) ) #define PB push_back #define MP make_pair #define ST first #define ND second #define INF 1000000001 using namespace std; typedef long long int LLI; typedef pair < int , int > PII; typedef pair < LLI , LLI > PLL; typedef vector < int > VI; typedef vector < bool > VB; typedef vector < PII > VP; typedef vector < LLI > VL; typedef vector < PLL > VPL; typedef vector < VI > VVI; typedef vector < VL > VVL; typedef vector < VB > VVB; typedef VVI Matrix; Matrix zero(int n, int m) { Matrix ans(n); FORE(i,ans) ans[i].resize(m,0); return ans; } Matrix identity(int n) { Matrix ans = zero(n, n); FOR(i,0,n-1) ans[i][i] = 1; return ans; } Matrix operator *(const Matrix &a, const Matrix &b) { int n = SIZE(a), k = SIZE(a[0]), m = SIZE(b[0]); Matrix ans = zero(n, m); FOR(i,0,n-1) FOR(j,0,k-1) FOR(t,0,m-1) ans[i][t] = min(1, ans[i][t] + a[i][j] * b[j][t]); return ans; } /*************************************************************************/ int main() { ios_base::sync_with_stdio(0); int n, b, r; cin >> n >> b >> r; Matrix M(n); FOR(i,0,n-1) FOR(j,0,n-1) { char b; cin >> b; M[i].PB(b - '0'); } VB robot(n,0); while (r--) { int x; cin >> x; x--; robot[x] = 1; } Matrix C = identity(n); int maxOp = (100 * 1000 * 1000) / (n * n * n); FOR(i,0,maxOp) { bool good = 1; FOR(rob,0,n-1) if (robot[rob]) FOR(j,b,n-1) if (C[rob][j]) good = 0; if (good) { cout << i; return 0; } C = C * M; } cout << -1; return 0; } /*************************************************************************/ |