fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define FOR(i,a,b) for(int i = (a); i <= (b); ++i)
  4. #define FORD(i,a,b) for(int i = (a); i >= (b); --i)
  5. #define RI(i,n) FOR(i,1,(n))
  6. #define REP(i,n) FOR(i,0,(n)-1)
  7. #define mini(a,b) a=min(a,b)
  8. #define maxi(a,b) a=max(a,b)
  9. #define mp make_pair
  10. #define pb push_back
  11. #define st first
  12. #define nd second
  13. #define sz(w) (int) w.size()
  14. typedef vector<int> vi;
  15. typedef long long ll;
  16. typedef long double ld;
  17. typedef pair<int,int> pii;
  18. const int inf = 1e9 + 1375;
  19. const int nax = 150;
  20.  
  21. int orig[nax], dest[nax], lim[nax];
  22. bool sure[nax];
  23. const int K = 50;
  24.  
  25. struct Matrix {
  26. 	ll t[nax][3];
  27. 	Matrix(){ REP(i, nax) REP(j, 3) t[i][j] = 0; }
  28. 	Matrix operator * (const Matrix & b) const {
  29. 		ll t2[nax][3];
  30. 		REP(i, nax) REP(j, 3) t2[i][j] = 0;
  31. 		REP(i, nax) REP(j, 3) REP(k, K)
  32. 			if(b.t[i][j] & (1LL << k))
  33. 				t2[j*K+k][i/K] |= (1LL << (i%K));
  34. 		Matrix res;
  35. 		REP(i, nax) REP(k, nax) {
  36. 			bool ok = false;
  37. 			REP(j, 3) if(t[i][j] & t2[k][j]) ok = true;
  38. 			if(ok)
  39. 				res.t[i][k/K] |= (1LL << (k%K));
  40. 		}
  41. 		return res;
  42. 	}
  43. };
  44.  
  45. int main() {
  46. 	int n, m;
  47. 	scanf("%d%d", &n, &m);
  48. 	REP(i, m) {
  49. 		scanf("%d%d%d", &orig[i], &dest[i], &lim[i]);
  50. 		orig[i]--;
  51. 		dest[i]--;
  52. 	}
  53. 	int prv = 0;
  54. 	sure[0] = true;
  55. 	while(true) {
  56. 		int nxt = inf;
  57. 		REP(i, m) if(lim[i] > prv) mini(nxt, lim[i]);
  58. 		int diff = nxt - prv;
  59. 		Matrix res;
  60. 		REP(i, n) res.t[i][i/K] |= (1LL << (i%K));
  61. 		Matrix a;
  62. 		REP(i, m) if(lim[i] < nxt)
  63. 			a.t[orig[i]][dest[i]/K] |= (1LL << (dest[i]%K));
  64. 		a.t[n-1][(n-1)/K] |= (1LL << ((n-1)%K));
  65. 		Matrix a0 = a;
  66. 		while(diff) {
  67. 			if(diff % 2) res = res * a;
  68. 			a = a * a;
  69. 			diff /= 2;
  70. 		}
  71. 		ll ple[3];
  72. 		REP(i, 3) ple[i] = 0;
  73. 		REP(i, n) if(sure[i]) REP(j, 3)
  74. 			ple[j] |= res.t[i][j];
  75. 		if(ple[(n-1)/K] & (1LL << ((n-1)%K))) {
  76. 			//puts("ta");
  77. 			a = a0;
  78. 			int memo = prv;
  79. 			while(true) {
  80. 				//printf("%lld\n", a.t[1][0]);
  81. 				++prv;
  82. 				REP(i, n) if(sure[i] && (a.t[i][(n-1)/K] & (1LL << ((n-1)%K)))) {
  83. 					printf("%d\n", prv);
  84. 					return 0;
  85. 				}
  86. 				if(prv > memo + n + 155) {
  87. 					puts("Impossible");
  88. 					return 0;
  89. 				}
  90. 				a = a * a0;
  91. 			}
  92. 		}
  93. 		bool ok = false;
  94. 		REP(i, n) sure[i] = (ple[i/K] & (1LL << (i%K)));
  95. 		REP(i, n) ok |= sure[i];
  96. 		if(!ok) {
  97. 			puts("Impossible");
  98. 			return 0;
  99. 		}
  100. 		prv = nxt;
  101. 	}
  102. 	return 0;
  103. }
  104.  
Success #stdin #stdout 0.02s 3468KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Impossible
https://ideone.com/6DVME8
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!