Advertisement
Guest User

Bell

a guest
Nov 14th, 2019
270
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.57 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define endl '\n'
  5. #define INF 0x3fffffff
  6. #define Distance(x1, y1, x2, y2) ((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2))
  7.  
  8. vector< vector< pair< int, int > > > Edges;
  9. vector< pair< int, int > > Points;
  10. set< int > coins;
  11. int T, N, M;
  12.  
  13. vector< int > Bellzao(){
  14. vector< int > weight(N, INF), next_w(N, INF), past(N, INF), path;
  15. set< int > now, next;
  16.  
  17. weight[N - 1] = 0;
  18. past[N - 1] = N - 1;
  19. next.insert(N - 1);
  20.  
  21. for(int l = 0; l < N && !next.empty(); l++){
  22. now = set< int >(next.begin(), next.end()); next.clear();
  23.  
  24. for(int from : now)
  25. for(pair< int, int > e : Edges[from])
  26. if(weight[from] + e.second < next_w[e.first]){
  27. past[e.first] = from;
  28. next.insert(e.first);
  29. next_w[e.first] = weight[from] + e.second;
  30. }
  31.  
  32. weight = vector< int >(next_w.begin(), next_w.end());
  33. }
  34.  
  35. if(next.empty()){
  36. int ver = 0;
  37.  
  38. while(ver != N - 1){
  39. ver = past[ver];
  40. path.push_back(ver);
  41. }
  42. path.push_back(weight[0]);
  43. }
  44. return path;
  45. }
  46.  
  47. int main(){
  48. ios::sync_with_stdio(false); cin.tie(0);
  49. vector< int > answer;
  50. int temp;
  51. cin >> T;
  52.  
  53. for(int k = 0; k < T; k++){
  54. coins.clear(); Edges.clear(); Points.clear();
  55.  
  56. cin >> N;
  57.  
  58. Edges = vector< vector< pair< int, int > > >(N);
  59. Points = vector< pair< int, int > >(N, make_pair(0, 0));
  60.  
  61. for(int i = 0; i < N; i++)
  62. cin >> Points[i].first >> Points[i].second;
  63.  
  64.  
  65. for(cin >> M; M > 0; M--){
  66. cin >> temp;
  67. coins.insert(temp);
  68. }
  69.  
  70. for(int i = 0, j; i < N; i++)
  71. for(cin >> j; j > 0; j--){
  72. cin >> temp;
  73. Edges[temp].push_back(make_pair(i, Distance(Points[i].first, Points[i].second, Points[temp].first, Points[temp].second)));
  74. }
  75.  
  76. for(int c : coins)
  77. for(pair< int, int > &d : Edges[c])
  78. d.second *= -1;
  79.  
  80. for(int i = 0; i < N; i++)
  81. sort(Edges[i].begin(), Edges[i].end());
  82.  
  83. answer = Bellzao();
  84.  
  85. if(!answer.empty()){
  86. cout << answer[answer.size() - 1] << " 0";
  87.  
  88. for(int i = 0; i < answer.size() - 1; i++)
  89. cout << " " << answer[i];
  90. cout << endl;
  91. }
  92. else
  93. cout << "LOOP" << endl;
  94. }
  95. return 0;
  96. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement