Guest User

Untitled

a guest
Oct 20th, 2018
113
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.26 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <stdio.h>
  4. #include <limits.h>
  5. #include <math.h>
  6. #include <queue>
  7. #include <string.h>
  8. using namespace std;
  9. int n;
  10. vector<pair<int,int> > *graph;
  11. unsigned long* costs;
  12.  
  13. bool* hasHotel;
  14.  
  15.  
  16. class Node{
  17. public:
  18. bool operator> ( const Node & rhs ) const
  19. { return cost < rhs.cost; }
  20. bool operator == ( const Node & rhs ) const
  21. { return cost == rhs.cost; }
  22. bool operator< ( const Node & rhs ) const
  23. { return cost > rhs.cost; }
  24. bool operator <= ( const Node & rhs ) const
  25. { return cost >= rhs.cost; }
  26. bool operator >= ( const Node & rhs ) const
  27. { return cost <= rhs.cost; }
  28. void set(int c, int i){
  29. cost = c;
  30. index = i;
  31. }
  32. int getCost(){return cost;}
  33. int getIndex(){return index;}
  34.  
  35. private :
  36. int cost;
  37. int index;
  38. };
  39.  
  40.  
  41. void Dijestra(){
  42. bool visited [n];
  43. costs = new unsigned long[n];
  44. int parent[n];
  45. bool bits[n];
  46. bits[0] = false;
  47. for (int i = 1;i < n;i++){
  48. costs[i] = ULONG_MAX;
  49. visited[i] = false;
  50. parent[i] =0;
  51. bits[i] = false;
  52. }
  53. costs[0] = 0;
  54.  
  55. parent[0] = 0;
  56.  
  57. priority_queue<Node> pr1;
  58. Node n1 ;
  59. n1.set(0, 0);
  60. pr1.push(n1);
  61.  
  62. while (!pr1.empty()){
  63. Node t = pr1.top();
  64. int index =t.getIndex();
  65. int parCost = t.getCost();
  66. pr1.pop();
  67. visited[index]= true;
  68. for (int i = 0;i < graph[index].size(); i++){
  69. pair<int , int> temp = graph[index].at(i);
  70. if (!visited[temp.first]){
  71. if (hasHotel[index] && (temp.second+ costs[index]) > 600){
  72. if (costs[temp.first] >temp.second){
  73. costs[temp.first] = temp.second;
  74. parent[temp.first] = index;
  75. Node nNode;
  76. nNode.set(temp.second, temp.first);
  77. pr1.push(nNode);
  78. bits[index] = true;
  79. }
  80. }
  81. else {
  82. if (costs[temp.first] >temp.second+ costs[index]){
  83. costs[temp.first] = temp.second+ costs[index];
  84. parent[temp.first] = index;
  85. Node nNode;
  86. nNode.set(temp.second+ costs[index], temp.first);
  87. pr1.push(nNode);
  88. bits[index] = false;
  89. }
  90. }
  91. }
  92. }
  93. }
  94. vector<int> path;
  95. for (int i = n-1; i != 0;){
  96. path.push_back(i+1);
  97. i = parent[i];
  98. }
  99. path.push_back(1);
  100.  
  101. int count = 0;
  102. for (int i = path.size() - 1; i >= 0; i--){
  103. if (hasHotel[path.at(i) - 1] && bits[index]){
  104. count++;
  105. tx = -1*costs[path.at(i) - 1];
  106. cout << tx<<endl;
  107. }
  108. }
  109. if (costs[n-1] > 600)
  110. cout << -1<<endl;
  111. else
  112. if (array[n-1] < 600)
  113. cout <<0<<endl;
  114. else
  115. cout << count<<endl;
  116. }
  117.  
  118. void get(){
  119. scanf("%d", &n);
  120. while (n != 0){
  121. int k;
  122. scanf("%d", &k);
  123. hasHotel =new bool [n];
  124. for (int i =0;i < n;i++)
  125. hasHotel[i] = false;
  126. for (int i = 0; i < k;i++){
  127. int temp;
  128. scanf("%d", &temp);
  129. hasHotel[temp-1] = true;
  130. }
  131. int edges;
  132. scanf("%d", &edges);
  133. graph = new vector<pair<int,int> >[n];
  134. int from , to, wigth;
  135. for (int i = 0;i < edges; i++){
  136. scanf("%d%d%d", &from , &to, &wigth);
  137. pair<int, int> p1;
  138. p1.first =to - 1;
  139. p1.second = wigth;
  140. graph[from -1].push_back(p1);
  141. }
  142. Dijestra();
  143.  
  144. delete []hasHotel;
  145. delete [] costs;
  146. delete []graph;
  147. scanf("%d", &n);
  148. }
  149. }
  150.  
  151.  
  152.  
  153. int main()
  154. {
  155. get();
  156. /*graph = new vector<pair<int,int> >[10];
  157. vector<pair<int,int> > p1;
  158. pair<int , int> par;
  159. par.first = 4;
  160. par.second = 1;
  161. p1.push_back(par);
  162. graph[0] = p1;
  163. pair<int , int> parc = p1.at(0);
  164. cout << parc.first<<" "<<parc.second<<endl;
  165. //t();*/
  166. return 0;
  167. }
  168. /*graph = new vector<pair<int,double> >[10];
  169. vector<pair<int,double> > p1;
  170. pair<int , double> par;
  171. par.first = 4;
  172. par.second = 1.5;
  173. p1.push_back(par);
  174. graph[0] = p1;
  175. t();*/
Add Comment
Please, Sign In to add comment