• API
• FAQ
• Tools
• Archive
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);
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.
84.
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.

Top