UVa 10496

#include<bits/stdc++.h>
using namespace std;

typedef unsigned long long int  ull;
typedef long long int      ll;
typedef vector<int>        vi;
typedef vector<ll>         vll;
typedef vector<vi>         vvi;
typedef pair<int,int >     pii;
typedef vector< pii >      vpii;
typedef set<int>           sti;

#define sc                 scanf
#define pf                 printf
#define sci(n)             scanf("%d",&n)
#define scl(n)             scanf("%lld",&n)
#define scd(n)             scanf("%lf",&n)
#define scs(s)             scanf("%s",s)
#define pfi(n)             printf("%d",n)
#define pfl(n)             printf("%lld",n)
#define pff(n)             cout<<n
#define line               printf("\n")
#define spc                printf(" ")
#define loop(i,x,y)        for(int i=int(x); i<=int(y); i++)
#define rloop(i,y,x)       for(int i=int(y); i>=int(x); i--)
#define cspf(i)            printf("Case %d: ", i)
#define pb                 push_back
#define mp                 make_pair
#define ff                 first
#define ss                 second
#define all(v)             v.begin(),v.end()
#define rall(v)            v.rbegin(),v.rend()
#define read()             freopen("input.txt", "r", stdin)
#define write()            freopen("output.txt", "w", stdout)
/// Constants
#define eps                1e-9
#define PI                 acos(-1.0)  // 3.1415926535897932
#define MAX                1000009

bool chk[20];
vpii vt;
int mn=MAX;

void solve(int node,int sum,int n,int cnt)
{
    if(cnt==n){
        sum+=(abs(vt[node].ff-vt[0].ff)+abs(vt[node].ss-vt[0].ss));
        mn=min(mn,sum);
        return;
    }
    loop(i,1,n){
        if(!chk[i]){
            chk[i]=1;
            int s=sum+(abs(vt[node].ff-vt[i].ff)+abs(vt[node].ss-vt[i].ss));
            solve(i,s,n,cnt+1);
            chk[i]=0;
        }
    }
}

int main()
{
    read();
    write();
    int tc;
    cin>>tc;
    while(tc--){
        memset(chk,0,sizeof chk);
        vt.clear();
        mn=MAX;
        int row,col,a,b,n;
        cin>>row>>col;
        cin>>a>>b;
        chk[0]=1;
        vt.pb(mp(a,b));
        cin>>n;
        int x,y;
        loop(i,1,n){
            cin>>x>>y;
            vt.pb(mp(x,y));
        }
        solve(0,0,n,0);
        cout<<"The shortest path has length "<<mn<<endl;
    }
    return 0;
}