Guest User

Untitled

a guest
Sep 10th, 2015
568
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <fstream>
  3. #include <sstream>
  4.  
  5. #include <vector>
  6. #include <set>
  7. #include <bitset>
  8. #include <map>
  9. #include <deque>
  10. #include <string>
  11.  
  12. #include <algorithm>
  13. #include <numeric>
  14.  
  15. #include <cstdio>
  16. #include <cassert>
  17. #include <cstdlib>
  18. #include <cstring>
  19. #include <ctime>
  20. #include <cmath>
  21.  
  22. #define pb push_back
  23. #define pbk pop_back
  24. #define mp make_pair
  25. #define fs first
  26. #define sc second
  27. #define all(x) (x).begin(), (x).end()
  28. #define foreach(i, a) for (__typeof((a).begin()) i = (a).begin(); i != (a).end(); ++i)
  29. #define len(a) ((int) (a).size())
  30.  
  31. #ifdef CUTEBMAING
  32. #define eprintf(...) fprintf(stderr, __VA_ARGS__)
  33. #else
  34. #define eprintf(...) 42
  35. #endif
  36.  
  37. using namespace std;
  38.  
  39. typedef long long int64;
  40. typedef long double ld;
  41. typedef unsigned long long lint;
  42.  
  43. const int inf = (1 << 30) - 1;
  44. const int64 linf = (1ll << 62) - 1;
  45. const int N = 160;
  46. const int K = 30;
  47.  
  48. struct edges {
  49.     int u, v;
  50. };
  51.  
  52. int n, m;
  53. map<int, vector<edges>> g;
  54. vector<pair<int, vector<edges>>> events;
  55.  
  56. bitset<N> mat[K][N];
  57.  
  58. bitset<N> temp[N];
  59.  
  60. void mul(bitset<N> a[N], bitset<N> b[N], bitset<N> c[N]) {
  61.     for (int i = 0; i < n; i++) {
  62.         for (int j = 0; j < n; j++) {
  63.             temp[j].set(i, b[i].test(j));
  64.         }
  65.     }
  66.     for (int i = 0; i < n; i++) {
  67.         for (int j = 0; j < n; j++) {
  68.             c[i].set(j, (a[i] & temp[j]).any());
  69.         }
  70.     }
  71. }
  72.  
  73. int dist[N][N];
  74. bool cur[N], ncur[N];
  75.  
  76. void apply(bitset<N> a[N]) {
  77.     fill_n(ncur, n, 0);
  78.     for (int i = 0; i < n; i++) {
  79.         if (cur[i]) {
  80.             for (int j = 0; j < n; j++) {
  81.                 if (a[i].test(j)) {
  82.                     ncur[j] = true;
  83.                 }
  84.             }
  85.         }
  86.     }
  87.     memcpy(cur, ncur, sizeof(bool) * n);
  88. }
  89.  
  90. int main() {
  91.     cin >> n >> m;
  92.     for (int i = 0; i < m; i++) {
  93.         int a, b, d; cin >> a >> b >> d;
  94.         g[d].pb({a - 1, b - 1});
  95.     }
  96.     g[0].pb({n - 1, n - 1});
  97.     g[inf].pb({n - 1, n - 1});
  98.     events = vector<pair<int, vector<edges>>>(all(g));
  99.     for (int i = 0; i < n; i++) {
  100.         for (int j = 0; j < n; j++) {
  101.             dist[i][j] = inf;
  102.         }
  103.         dist[i][i] = 0;
  104.         mat[0][i].reset();
  105.     }
  106.     cur[0] = 1;
  107.     int ans = inf;
  108.     for (int i = 0; i < len(events) - 1; i++) {
  109.         int curTime = events[i].fs, nextTime = events[i + 1].fs;
  110.         for (edges e : events[i].sc) {
  111.             mat[0][e.u].set(e.v, true);
  112.             for (int j = 0; j < n; j++) {
  113.                 for (int z = 0; z < n; z++) {
  114.                     dist[j][z] = min(dist[j][z], dist[j][e.u] + dist[e.v][z] + 1);
  115.                 }
  116.             }
  117.         }
  118.         for (int i = 0; i < n; i++) {
  119.             if (cur[i]) {
  120.                 ans = min(ans, curTime + dist[i][n - 1]);
  121.             }
  122.         }
  123.         for (int j = 1; j < K; j++) {
  124.             mul(mat[j - 1], mat[j - 1], mat[j]);
  125.         }
  126.         int delta = nextTime - curTime;
  127.         for (int j = K - 1; j >= 0; j--) {
  128.             if (delta >= (1 << j)) {
  129.                 apply(mat[j]);
  130.                 delta -= (1 << j);
  131.             }
  132.         }
  133.     }
  134.     if (ans >= inf) {
  135.         cout << "Impossible" << endl;
  136.     } else {
  137.         cout << ans << endl;
  138.         eprintf("ans = %d\n", ans);
  139.     }
  140.     return 0;
  141. }
RAW Paste Data