SHARE
TWEET

Bell

a guest Nov 14th, 2019 67 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  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. }
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