Advertisement
Guest User

Untitled

a guest
Jul 16th, 2017
118
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.97 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(N+1, MAX_INT);
  21.  
  22. // min distance contiene le distanze 1,2,3,4.. il numero di nodi passati per arrivare li
  23. vector<int> min_distance( N+1, MAX_INT );
  24. min_distance[ W ] = 0;
  25.  
  26. // ricorda: ogni volta che cambia il collegamento, il par
  27.  
  28. vector< vector< collegamento> > grafo(N+1);
  29.  
  30. for(int i = 0; i < M; i++)
  31. {
  32. int temp = arco_da[i];
  33. collegamento f;
  34. f.to = arco_a[i];
  35. f.capacita = capacita[i];
  36. grafo[temp].push_back(f);
  37. f.to = temp;
  38. grafo[arco_a[i]].push_back(f);
  39. }
  40.  
  41. // rappresenta peso, nodo attuale
  42. priority_queue< ii, vector<ii>, greater<ii> > pq; pq.push({0, W});
  43.  
  44. while(!pq.empty())
  45. {
  46. ii v = pq.top(); pq.pop();
  47. for(int i = 0 ; i < grafo[v.second].size(); i++)
  48. {
  49. collegamento u = grafo[v.second][i];
  50.  
  51. if(min_distance[v.second] + 1 < min_distance[u.to])
  52. {
  53. pq.push({min_distance[u.to] = min_distance[v.second] + 1, u.to});
  54. minCost[u.to] = min(u.capacita, minCost[v.second]);
  55.  
  56. }
  57. else if( (min_distance[v.second] + 1 == min_distance[u.to]))
  58. {
  59. int min1 = min(minCost[v.second], u.capacita);
  60.  
  61. if(min1 < minCost[u.to])
  62. {
  63. pq.push({min_distance[u.to] = min_distance[v.second] + 1, u.to});
  64. minCost[u.to] = min1;
  65.  
  66. }
  67. }
  68.  
  69. }
  70.  
  71. }
  72.  
  73. return minCost[L];
  74. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement