Advertisement
Guest User

Untitled

a guest
Feb 9th, 2017
147
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.84 KB | None | 0 0
  1. #include <vector>
  2. #include <queue>
  3. #include <deque>
  4. #include <stdio.h>
  5. #include <unordered_set>
  6. #include <utility>
  7. #include <string.h>
  8. #include <limits>
  9. using namespace std;
  10.  
  11. #define MAXN 1010
  12. #define MAXK 80
  13. #define MAXV 1000000
  14.  
  15. struct arco_t {
  16.     int u, v;
  17.     int t_piedi;
  18.     int t_bus;
  19.     int n_volontarie;
  20. };
  21. struct info_t {
  22.     int n, t, k;
  23.     bool operator< (const info_t& r) const {
  24.         return t > r.t;
  25.     }
  26. };
  27.  
  28. const int INF = numeric_limits<int>::max();
  29.  
  30. int N, T, S, E, K;
  31.  
  32. vector<vector<arco_t>> G;
  33.  
  34. int dist[MAXN][MAXK];
  35. bool solved[MAXN][MAXK];
  36. bool dijkstra(int v_max) {
  37.     for (int i = 0; i < N; i++) {
  38.         for (int j = 0; j <= K; j++) {
  39.             dist[i][j] = INF;
  40.             solved[i][j] = false;
  41.         }
  42.     }
  43.     priority_queue<info_t> Q;
  44.     Q.push({S, 0, K});
  45.     dist[S][K] = 0;
  46.     while (!Q.empty()) {
  47.         info_t c = Q.top();
  48.         Q.pop();
  49.  
  50.         //printf("Nodo %d @ t: %d, k:%d\n", c.n, c.t, c.k);
  51.         if (c.n == E) return true;
  52.  
  53.         solved[c.n][c.k] = true;
  54.  
  55.         // Se sto visitando questo nodo con un tempo minore dell'ultima volta
  56.         for (const arco_t& x : G[c.n]) {
  57.  
  58.             //printf("\tArco %d (t: %d, b: %d, v: %d)\n", x.v, x.t_piedi, x.t_bus, x.n_volontarie);
  59.             if (c.k > 0 && dist[x.v][c.k-1] > c.t + x.t_bus) {
  60.  
  61.                 // Se con l'autobus faccio in tempo ed ho almeno 1 biglietto
  62.                 if (c.t + x.t_bus < T && c.k > 0 && !solved[x.v][c.k-1]) {
  63.                     // Aggiungo alla lista
  64.                     Q.push({x.v, c.t+x.t_bus, c.k-1});
  65.                 }
  66.  
  67.             }
  68.             if (dist[x.v][c.k] > c.t + x.t_piedi) {
  69.  
  70.                 // Se a piedi faccio in tempo e ci sono al massimo v_max volontarie
  71.                 if (c.t + x.t_piedi < T && x.n_volontarie <= v_max && !solved[x.v][c.k]) {
  72.                     // Aggiungo alla lista
  73.                     Q.push({x.v, c.t+x.t_piedi, c.k});
  74.                 }
  75.             }
  76.         }
  77.  
  78.     }
  79.     return false;
  80. }
  81.  
  82. int avoid_volunteers(int subtask, int N, int M, int K, int S, int E, int T, int A[], int B[], int W[], int P[], int V[]) {
  83.     ::N = N;
  84.     ::T = T;
  85.     ::E = E;
  86.     ::K = K;
  87.     ::S = S;
  88.     G.resize(N);
  89.     int v_max = 0;
  90.     for (int i = 0; i < M; i++) {
  91.         v_max = max(v_max, V[i]);
  92.         G[A[i]].push_back({A[i], B[i], W[i], P[i], V[i]});
  93.         G[B[i]].push_back({B[i], A[i], W[i], P[i], V[i]});
  94.     }
  95.  
  96.     int start = 0;
  97.     int end = MAXV;
  98.  
  99.  
  100.     int last = INF;
  101.     while (start <= end) {
  102.         int mid = (start+end) / 2;
  103.         bool r = dijkstra(mid);
  104.         //printf("mid(%d) = %d\n", mid, r);
  105.         if (r == 1) {
  106.             last = min(mid, last);
  107.             end = mid-1;
  108.         }
  109.         else {
  110.             start = mid+1;
  111.         }
  112.     }
  113.     return (last == INF ? -1 : last);
  114. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement