SHARE
TWEET

grattacieli

MaxSandre Apr 8th, 2020 (edited) 42 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <stdio.h>
  3. #include <vector>
  4. #include <queue>
  5. using namespace std;
  6.  
  7. typedef pair<long long, long long> pi;
  8.  
  9. long long costruisci(int N, int M, vector<long long>& H, vector<int>& A, vector<int>& B, vector<int>& C) {
  10.     vector<vector<pi>> gr(N);
  11.     // creo la lista di adiacenza
  12.     for(long long i = 0; i < M;i++) {
  13.         gr[A[i]].push_back(make_pair(B[i],C[i]));
  14.     }
  15.  
  16.     priority_queue<pi,vector<pi>, greater<pi>> q;
  17.  
  18.     // parto dal primo palazzo
  19.     q.push(make_pair(H[0],0));
  20.  
  21.     /// utilizzare un vettore per monitorare i palazzi controllati rende la complessità quadratica, meglio usare un set   
  22.     vector<bool> vis(N,false);
  23.     bool finito = false;
  24.  
  25.     // memorizzo il nodo di partenza
  26.     int fir = 0;
  27.  
  28.     do {
  29.         while(!q.empty()) {
  30.             // prendo il primo palazzo nella coda
  31.             pi x = q.top();
  32.             q.pop();
  33.  
  34.             // ho visitato il nodo
  35.             vis[x.second] = true;
  36.  
  37.             // se il palazzo attuale rispetta i limiti e non è quello di partenza lo salto
  38.             if(x.first >= H[x.second] && x.second != fir) continue;
  39.  
  40.             // se il palazzo non rispetta i limiti gli assegno il più grande valore che rispetta i limiti
  41.             H[x.second] = x.first;
  42.             // controllo tutte le limitazioni impartite dal proprietario del palazzo attuale
  43.             for(long long i = 0; i < gr[x.second].size();i++) {
  44.                 // calcolo la massima altezza che può assumere il palazzo i-esimo
  45.                 long long da = x.first + gr[x.second][i].second;
  46.                 // se il palazzo supera questa altezza lo aggiungo alla coda
  47.                 if(H[gr[x.second][i].first] > da) {
  48.                     q.push(make_pair(da,gr[x.second][i].first));
  49.                 }
  50.             }
  51.         }
  52.  
  53.         // verifico che non siano rimasti palazzi da controllare
  54.         finito = true;
  55.         for(int i = 0; i< N&&finito;i++) {
  56.             if(!vis[i]) {
  57.                 finito = false;
  58.                 //inserisco nella coda il primo palazzo non controllato
  59.                 q.push(make_pair(H[i],i));
  60.                 fir = i;
  61.             }
  62.         }
  63.         // ripeto finché non avrò visitato tutti i nodi
  64.     }while(!finito);
  65.  
  66.     // calcolo e ritorno il risultato
  67.     long long somma=0;
  68.     for(int i = 0; i < N;i++) {
  69.         somma+=H[i];
  70.     }
  71.     return somma;
  72. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top