Solution UVA: 10496 - Collecting Beepers

 

Problem	Verdict	Lang	Time	Best	Rank	Submit Time
| discuss10496 - Collecting Beepers	Accepted	C++11	0.000	0.000	1722	1 mins ago

Suggest:

Throw away the TSP dynamic programming algorithm and we will have a super easy recursive + branch and bound problem (same problem 216)

#include<bits/stdc++.h>

#define X first

#define Y second

using namespace std;

int sum;

int n, cnt;

int res;

vector<bool> visited(9);

vector<pair<int, int>> a(9);

int dist(int u, int v){

    return abs(a[u].X-a[v].X) + abs(a[u].Y-a[v].Y);    

}

void dfs(int u, int sum){

   

    if (sum > res) return;

    bool finish= true;

    for(int v=1; v<=n; v++)

        if (v!=u and not visited[v]){

            finish= false;

           

           

            visited[v]= true;

                dfs(v, sum + dist(u,v));

            visited[v]= false;

       

        }

   

    if (finish) {

        if (res > sum + dist(u,1)){

            res= sum + dist(u,1);    

        }  

    }

}

int main(){

    ios::sync_with_stdio(false); cin.tie(nullptr);

    int t;  cin >> t;

    while(t--){

        int l, r;

        cin >> l >> r;

        cin >> l >> r;  

        a[1].X= l, a[1].Y= r;

       

        cin >> n; n++;

        for(int i=2; i<=n; i++)

            cin >> a[i].X >> a[i].Y;

       

        res= 1000111000;

       

        sum= 0;

        for(int j=1; j<=n; j++) visited[j]= false;

       

        visited[1]= true;

        dfs(1, 0);

        cout<<"The shortest path has length "<<res<<"\n";

     

    }

}