Advertisement
Guest User

Untitled

a guest
Jul 16th, 2017
84
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.65 KB | None | 0 0
  1. #include<vector>
  2. #include <utility>
  3. #include<queue>
  4. #include<iostream>
  5.  
  6. using namespace std;
  7.  
  8. typedef pair<int, int> ii;
  9.  
  10. struct collegamento
  11. {
  12. int to;
  13. int capacita;
  14. };
  15.  
  16. int Analizza(int N, int M, int W, int L, int arco_da[], int arco_a[], int capacita[], int R, int C) {
  17.  
  18. // min cost contiene i megabit minimi per arrivare li
  19. int MAX_INT = 2000000000;
  20. vector<int> minCost;
  21. minCost.resize(N+1, MAX_INT);
  22.  
  23. // min distance contiene le distanze 1,2,3,4.. il numero di nodi passati per arrivare li
  24. vector<int> min_distance( N+1, MAX_INT );
  25. min_distance[ W ] = 0;
  26.  
  27. // ricorda: ogni volta che cambia il collegamento, il par
  28.  
  29. vector< vector< collegamento> > grafo(N+1);
  30.  
  31. for(int i = 0; i < M; i++)
  32. {
  33. int temp = arco_da[i];
  34. collegamento f;
  35. f.to = arco_a[i];
  36. f.capacita = capacita[i];
  37. grafo[temp].push_back(f);
  38. f.to = temp;
  39. grafo[arco_a[i]].push_back(f);
  40. }
  41.  
  42. // rappresenta peso, nodo attuale
  43. priority_queue< ii, vector<ii>, greater<ii> > pq; pq.push({0, W});
  44.  
  45. while(!pq.empty())
  46. {
  47. ii v = pq.top(); pq.pop();
  48. for(int i = 0 ; i < grafo[v.second].size(); i++)
  49. {
  50. collegamento u = grafo[v.second][i];
  51.  
  52. if(min_distance[v.second] + 1 < min_distance[u.to] || (min_distance[v.second] + 1 == min_distance[u.to] && u.capacita > minCost[v.second]))
  53. {
  54. pq.push({min_distance[u.to] = min_distance[v.second] + 1, u.to});
  55. minCost[u.to] = min(u.capacita, minCost[v.second]);
  56.  
  57. }
  58. }
  59.  
  60. }
  61.  
  62. return minCost[L];
  63. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement