Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define endl '\n'
- #define INF 0x3fffffff
- #define Distance(x1, y1, x2, y2) ((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2))
- vector< vector< pair< int, int > > > Edges;
- vector< pair< int, int > > Points;
- set< int > coins;
- int T, N, M;
- vector< int > Bellzao(){
- vector< int > weight(N, INF), next_w(N, INF), past(N, INF), path;
- set< int > now, next;
- weight[N - 1] = 0;
- past[N - 1] = N - 1;
- next.insert(N - 1);
- for(int l = 0; l < N && !next.empty(); l++){
- now = set< int >(next.begin(), next.end()); next.clear();
- for(int from : now)
- for(pair< int, int > e : Edges[from])
- if(weight[from] + e.second < next_w[e.first]){
- past[e.first] = from;
- next.insert(e.first);
- next_w[e.first] = weight[from] + e.second;
- }
- weight = vector< int >(next_w.begin(), next_w.end());
- }
- if(next.empty()){
- int ver = 0;
- while(ver != N - 1){
- ver = past[ver];
- path.push_back(ver);
- }
- path.push_back(weight[0]);
- }
- return path;
- }
- int main(){
- ios::sync_with_stdio(false); cin.tie(0);
- vector< int > answer;
- int temp;
- cin >> T;
- for(int k = 0; k < T; k++){
- coins.clear(); Edges.clear(); Points.clear();
- cin >> N;
- Edges = vector< vector< pair< int, int > > >(N);
- Points = vector< pair< int, int > >(N, make_pair(0, 0));
- for(int i = 0; i < N; i++)
- cin >> Points[i].first >> Points[i].second;
- for(cin >> M; M > 0; M--){
- cin >> temp;
- coins.insert(temp);
- }
- for(int i = 0, j; i < N; i++)
- for(cin >> j; j > 0; j--){
- cin >> temp;
- Edges[temp].push_back(make_pair(i, Distance(Points[i].first, Points[i].second, Points[temp].first, Points[temp].second)));
- }
- for(int c : coins)
- for(pair< int, int > &d : Edges[c])
- d.second *= -1;
- for(int i = 0; i < N; i++)
- sort(Edges[i].begin(), Edges[i].end());
- answer = Bellzao();
- if(!answer.empty()){
- cout << answer[answer.size() - 1] << " 0";
- for(int i = 0; i < answer.size() - 1; i++)
- cout << " " << answer[i];
- cout << endl;
- }
- else
- cout << "LOOP" << endl;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement