QuXiao

题目来源：

PKU 1018 Communication System

 

算法分类：

枚举+贪心

 

原文：

Communication System

Time Limit:1000MS  Memory Limit:10000K

Description

We have received an order from Pizoor Communications Inc. for a special communication system. The system consists of several devices. For each device, we are free to choose from several manufacturers. Same devices from two manufacturers differ in their maximum bandwidths and prices.
By overall bandwidth (B) we mean the minimum of the bandwidths of the chosen devices in the communication system and the total price (P) is the sum of the prices of all chosen devices. Our goal is to choose a manufacturer for each device to maximize B/P.

Input

The first line of the input file contains a single integer t (1 ≤ t ≤ 10), the number of test cases, followed by the input data for each test case. Each test case starts with a line containing a single integer n (1 ≤ n ≤ 100), the number of devices in the communication system, followed by n lines in the following format: the i-th line (1 ≤ i ≤ n) starts with mi (1 ≤ mi ≤ 100), the number of manufacturers for the i-th device, followed by mi pairs of positive integers in the same line, each indicating the bandwidth and the price of the device respectively, corresponding to a manufacturer.

Output

Your program should produce a single line for each test case containing a single number which is the maximum possible B/P for the test case. Round the numbers in the output to 3 digits after decimal point.

Sample Input

1 3

3 100 25 150 35 80 25

2 120 80 155 40

2 100 100 120 110

 

Sample Output

0.649

 

Source

Tehran 2002, First Iran Nationwide Internet Programming Contest

 

 

中文描述：

你需要购买n种设备来组一个通信系统，每一种设备，又是由一些不同的制造商生产的，不同制造商生产的同种设备会有不同的带宽和价格。现在你要在每一个设备的制造商中选一个，使得购买的n种设备，它们带宽的最小值与价格之和的比最大。

 

题目分析：

一开始想到的就是暴搜，但是搜索的深度达到100，时间肯定是不允许的。想要解决这题，必须找到一个好的查找策略。再想想看这题的特点，最后的答案，带宽是选取所有设备中的最小值，而价格是选取所有设备的价格总和。如果某个制造商生产的某种设备，它的带宽较高而价格较低，那么选取它的可能性就比较大。再进一步说，如果所选取的n种设备的带宽的最小值b已经确定，那么对于某种设备，我们就可以在那些生产这种设备的，带宽大于等于b的制造商中进行选择。当然是选那个价格最低的设备，因为答案的分子已经确定为b，所以分母越小越好。看来只要枚举b，再对于每个设备贪心的选择最小价格就可以了，时间复杂度为O（mnB），B为带宽枚举的数量。但问题又来了，应该怎么枚举带宽，题目中并未给出带宽的取值范围，如果从0..maxB一个一个枚举的话，既费时又会造成过多重复情况（如果枚举那些在输入中出现的两个连续带宽之间的值，最后的答案是一样的）。所以我们应该采取某个方法记录输入中出现过的带宽（STL中的set是个不错的选择），再枚举这些带宽。在枚举中，可能出现这种情况：枚举b，选择了n种设备，但选择的所有设备的带宽都大于b，那么最终用b/price就不是这种情况的正确答案。其实不用担心，因为正确答案一定大于b/price。假设上面这种情况的实际带宽最小值是b’，那个当我们再去枚举b’时，至少有一个设备的带宽等于b’，这次得到的答案也就是上面那种情况的答案，所以最终还是能得到正确解。

 

代码：

#include <iostream>

#include <map>

#include <set>

#include <climits>

using namespace std;

 

const int MAX = 105;

 

struct Info

{

                int band, price;

};

 

struct Device

{

                int manuNum;

                Info info[MAX];

                map<int, int> minPrice;                 //map[i] = j 表示带宽>=i的最小价格是j

                int minBand, maxBand;

};

 

Device device[MAX];

int deviceNum;

set<int> band;                                                                  //输入中出现过的band

set<int>::iterator start, end;

int maxBand, minBand;                                 //需要枚举的band的最值

 

int cmp( const void *a , const void *b )

{

                Info *c = (Info *)a;

                Info *d = (Info *)b;

                if(c->band != d->band)

                                return d->band - c->band;

                else

                                return c->price - d->price;

}

 

void Input ()

{

                int i, j, max, min;

                band.clear();

                cin>>deviceNum;

                for (i=0; i<deviceNum; i++)

                {

                                device[i].minBand = INT_MAX;

                                device[i].maxBand = -1;

                                cin>>device[i].manuNum;

                                for (j=0; j<device[i].manuNum; j++)

                                {

                                                cin>>device[i].info[j].band>>device[i].info[j].price;

                                                band.insert(device[i].info[j].band);

                                                if ( device[i].info[j].band > device[i].maxBand )

                                                                device[i].maxBand = device[i].info[j].band;

                                                if ( device[i].info[j].band < device[i].minBand )

                                                                device[i].minBand = device[i].info[j].band;

                                }

                                                               

                }

}

 

void Pre ()                                           //预处理

{

                int i, j, min, b;

                //计算所需枚举的带宽的最值

                maxBand = INT_MAX;                   //maxBand为所有设备带宽最大值的最小值

                minBand = INT_MAX;                    //minBand为所有设备带宽最小值的最小值

                for (i=0; i<deviceNum; i++)

                {

                                if ( device[i].maxBand < maxBand )

                                                maxBand = device[i].maxBand;

                                if ( device[i].minBand < minBand )

                                                minBand = device[i].minBand;

                }

 

                //对于每个设备，找到带宽大于等于某一值的最小价格

                for (i=0; i<deviceNum; i++)

                {

                                //band从大到小，band相等时price从小到大

                                qsort(device[i].info, device[i].manuNum, sizeof(Info), cmp);

                                device[i].minPrice.clear();

                                min = device[i].info[0].price;

                                b = device[i].info[0].band;

                                device[i].minPrice[b] = min;

                                for (j=1; j<device[i].manuNum; j++)

                                {

                                                if ( device[i].info[j].band == b )

                                                                continue;

                                                if ( device[i].info[j].price < min )

                                                {

                                                                min = device[i].info[j].price;

                                                }

                                                b = device[i].info[j].band;

                                                device[i].minPrice[b] = min;

                                }

                }             

}

 

void Solve ()

{

                Pre();

 

                int b, i, totalPrice;

                double rate, ans;

                map<int, int>::iterator it;

                ans = 0;

                start = band.find(minBand);

                end = band.find(maxBand);

                end ++;

                while ( start != end )

                {

                                b = *start;

                                start ++;

                                totalPrice = 0;

                                for (i=0; i<deviceNum; i++)

                                {

                                                //找到带宽大于等于b的最小价格

                                                for (it=device[i].minPrice.begin(); it!=device[i].minPrice.end(); it++)

                                                {

                                                                if ( it->first >= b )

                                                                {

                                                                                totalPrice += it->second;

                                                                                break;

                                                                }

                                                }

 

                                }

                                rate = double(b) / totalPrice;

                                if ( rate > ans )

                                                ans = rate;

                }

 

                printf("%.3f\n", ans);

}

 

int main ()

{

                int test;

                cin>>test;

                while ( test -- )

                {

                                Input ();

                                Solve ();

                }

 

                return 0;

}

     摘要: 解题报告   题目来源： PKU 3513 Let's Go to the Movies   分类： 树形DP   原文： Let's Go to the Movies   Time Limit: 1000MS ...  阅读全文

解题报告

 

题目来源：

PKU 1505 Copying Books

 

算法分类：

DP

 

原文：

Copying Books

Description

Before the invention of book-printing, it was very hard to make a copy of a book. All the contents had to be re-written by hand by so called scribers. The scriber had been given a book and after several months he finished its copy. One of the most famous scribers lived in the 15th century and his name was Xaverius Endricus Remius Ontius Xendrianus (Xerox). Anyway, the work was very annoying and boring. And the only way to speed it up was to hire more scribers.

Once upon a time, there was a theater ensemble that wanted to play famous Antique Tragedies. The scripts of these plays were divided into many books and actors needed more copies of them, of course. So they hired many scribers to make copies of these books. Imagine you have m books (numbered 1, 2 ... m) that may have different number of pages (p1, p2 ... pm) and you want to make one copy of each of them. Your task is to divide these books among k scribes, k <= m. Each book can be assigned to a single scriber only, and every scriber must get a continuous sequence of books. That means, there exists an increasing succession of numbers 0 = b0 < b1 < b2, ... < b_k-1 <= bk = m such that i-th scriber gets a sequence of books with numbers between bi-1+1 and bi. The time needed to make a copy of all the books is determined by the scriber who was assigned the most work. Therefore, our goal is to minimize the maximum number of pages assigned to a single scriber. Your task is to find the optimal assignment.

Input

The input consists of N cases. The first line of the input contains only positive integer N. Then follow the cases. Each case consists of exactly two lines. At the first line, there are two integers m and k, 1 <= k <= m <= 500. At the second line, there are integers p1, p2, ... pm separated by spaces. All these values are positive and less than 10000000.

Output

For each case, print exactly one line. The line must contain the input succession p1, p2, ... pm divided into exactly k parts such that the maximum sum of a single part should be as small as possible. Use the slash character ('/') to separate the parts. There must be exactly one space character between any two successive numbers and between the number and the slash.

If there is more than one solution, print the one that minimizes the work assigned to the first scriber, then to the second scriber etc. But each scriber must be assigned at least one book.

Sample Input

2

9 3

100 200 300 400 500 600 700 800 900

5 4

100 100 100 100 100

Sample Output

100 200 300 400 500 / 600 700 / 800 900

100 / 100 / 100 / 100 100

Source

Central Europe 1998

 

 

中文描述：

题目大意是给你m（1…m）本书，每本书有Pm页，用k（k<=m）个员工来复印这些书。每本书只能分配给一个员工来复印，并且每个员工必须复印一段连续的书籍，每个员工复印的时间取决于所复印书籍的总页数。让你给出相应的分配，使得分配给员工的书籍页数的最大值尽量小。注意，如果有多种分配的方案，使得第一个员工的书籍页数尽量少，其次是第二个、第三个……以此类推。

 

题目分析：

我们可以从后往前推，最后一个员工，也就是第k个员工，他至少要复印第m本书，至多可以复印第k本到第m本（因为至少要分配给前k-1个员工每人一本书）。假设，第k名员工复制第i（k<=i<=m）本书到第m本书，那么，所有员工复印书籍的最小时间就为第k名员工所需的时间以及前k-1名员工复制前i-1本书所需最小时间的较大的那个时间。这样，问题的规模就从k个员工复印m本书减小到了k-1个员工复印i-1本书，而且求解过程中会不断遇到前a个员工复印前b本书的最小时间。为了减小问题的规模以及记录重复子问题的解，就可以用DP。

但仅仅算出最小时间的不够的，还要给出分配的方案，这个稍微有点繁琐。因为题目中说，如果有多种最优的分配方案，应该让前面的员工分配的页数尽量少。那么，可以从后推，在当前的员工所复印的书籍页数没有超过最大页数的情况下，让其复印的页数最大化。如果超过了最大页数，就把这本书分配给前一名员工。最后再按顺序将分配结果输出出来。

 

代码：

#include <cstdio>

#include <climits>

#include <cstring>

 

const int MAX = 505;

int book[MAX];

__int64 total[MAX];                        //1~n本书的页数

int k, m;

__int64 f[MAX][MAX];                  //f[i][j] = k 表示前i个人复制前j本书所需最少时间是k

__int64 max;

void Input ()

{

                scanf("%d%d", &m, &k);

                int i;

                for (i=1; i<=m; i++)

                                scanf("%d", &book[i]);

}

 

__int64 Sum (int s, int e)                                               //第s本书到第e本书的总页数

{

                return (total[e] - total[s-1]);

}

 

__int64 Max (__int64 a, __int64 b)

{

                return ( a>b?a:b );

}

 

__int64 Min (int x, int y)                                //前x个人复制前y本书所需的最少时间        x<=y

{

//考虑特殊情况

                if ( f[x][y] != -1 )

                                return f[x][y];

                if ( y == 0 )

                                return ( f[x][y] = 0 );

                if ( x == 0 )

                                return ( f[x][y] = INT_MAX );

 

                int i;

                __int64 temp;

                f[x][y] = INT_MAX;

                for (i=x-1; i<y; i++)

                {

//第x个人复制第i+1到第y本书与前x-1个人复制前i本书的时间较大的时间

                                temp = Max( Min(x-1, i), Sum(i+1, y) );                 

                                if ( temp < f[x][y] )

                                {

                                                f[x][y] = temp;

                                }

                }

                return f[x][y];

}

 

void Output ()

{

                int i, p;

                __int64 temp;

                int slash[MAX];

                max = f[k][m];

                memset(slash, 0, sizeof(slash));

                temp = 0;

                p = k;

                for (i=m; i>0; i--)

                {

                                //让后面的员工尽量复印最多的书籍

                                if ( temp + book[i] > max || i < p )

                                {

                                                slash[i] = 1;

                                                temp = book[i];

                                                p --;

                                }

                                else

                                {

                                                temp += book[i];

                                }

                }

 

                for (i=1; i<=m; i++)

                {

                                printf("%d", book[i]);

                                if ( slash[i] == 1 )

                                                printf(" / ");

                                else if ( i != m )

                                                printf(" ");

                }

                printf("\n");

}

 

void Solve ()

{

                int i, j;

                //预处理书籍页数的和

                total[0] = 0;

                for (i=1; i<=m; i++)

                                total[i] = total[i-1] + book[i];

 

                memset(f, -1, sizeof(f));

               

                Min(k, m);

               

                Output();

}

 

int main ()

{

                int test;

                scanf("%d", &test);

                while ( test-- )

                {

                                Input ();

                                Solve ();

                }

 

                return 0;

}

 

 

程序分析与心得：

时间复杂度O(n²)，空间复杂度O(n²)。

在用记忆化搜索解决DP问题时，往往比较符合人的思维，容易想到模型，编程比较简单。在解题过程中，除了可以按照常理顺着推，也可以尝试逆向思维，从最后的状态倒着推，这样可以使问题想得更加透彻，有比较好的效果。

题目大意：
    给你n个药的序列，牛从时间1开始吃药，在奇数时间吃药可以增加弹跳力，在偶数时间吃药则会减少弹跳力。在某一时间，你可以跳过一些药，但一旦吃过某种药，你就不能在选前面的药了。问你某一个吃药的序列，使牛最终的弹跳力最大。

思路：
    虽然题目不难，但思考题目的过程十分有意思。对于某种药，共有4中状态：在奇数时间吃、在奇数时间不吃、在偶数时间吃以及在偶数时间不吃。关键在于这4种状态之间的转移。因为如果跳过某种药是不需要花费时间的，所以在某2次的吃药时间内，时间相当于是静止的，一直维持在第1次吃药的时间段内。
    所以可用一数组max[i][2][2]表示状态，第i种药在奇/偶时间段内吃/不吃。可得状态转移可表示为：
    max[i][0][0] = Max (max[i-1][0][0], max[i-1][0][1]);
    max[i][0][1] = Max (max[i-1][1][0], max[i-1][1][1]) - high[i];
    max[i][1][0] = Max (max[i-1][1][0], max[i-1][1][1]);
    max[i][1][1] = Max (max[i-1][0][0], max[i-1][0][1]) + high[i];

代码：

#include <iostream>
using namespace std;

const int MAX = 150005;
int high[MAX];
int max[MAX][2][2];
int n;

void Input ()
{
    scanf("%d", &n);
    int i;
    for (i=1; i<=n; i++)
        scanf("%d", &high[i]);

}

int Max (int a, int b)
{
    return ( a>b?a:b );
}

void Solve ()
{
    int i;
    for (i=1; i<=n; i++)
    {
        max[i][0][0] = Max (max[i-1][0][0], max[i-1][0][1]);
        max[i][0][1] = Max (max[i-1][1][0], max[i-1][1][1]) - high[i];
        max[i][1][0] = Max (max[i-1][1][0], max[i-1][1][1]);
        max[i][1][1] = Max (max[i-1][0][0], max[i-1][0][1]) + high[i];
    }
    printf("%d\n", Max ( Max(max[n][0][0], max[n][0][1]), Max(max[n][1][0], max[n][1][1])) );
}

int main ()
{
    Input ();
    Solve ();

    return 0;
}

题目大意：
    给定n个连续的长度为1的矩形的高度h（1<=n<=100000，0<=hi<=1000000000），问你其中能构成的最大矩形的面积是多少。

思路：
    很显然，用DP。但关键是怎样表示状态，一开始想用一个二维数组min[][]表示从i～j的最小高度，面积就等于min[i][j]*(j-i+1)。但很不幸，根据题目给定的n的范围，这个二维数组根本无法创建。:(
    后来从论坛上得到提示，因为对于图中的某个面积最大的矩形，必然有一个最低的高度h[k]，即矩形的高等于h[k]，以第k块矩形的高度，最左边可以到达这个矩形的左边，最右边可以到达这个矩形的右边。所以，可以以每块矩形进行扩展，求出最左边和最右边（即两边的高度都大于等于这块的高度），得出面积s[i]，这样就可求出最大的s[i]了。

代码：

#include <cstdio>

const int MAX = 100005;
__int64 h[MAX];
__int64 left[MAX], right[MAX];        //left[i] = j表示第i个矩形以它的高度到达最左边的下标
int n;

bool Input ()
{
    scanf("%d", &n);
    if ( n == 0 )
        return false;
    int i;
    for (i=1; i<=n; i++)
        scanf("%I64d", &h[i]);
    h[0] = h[n+1] = -1;
    return true;
}

void Solve ()
{
    int i;
    __int64 temp, max;
    for (i=1; i<=n; i++)
    {
        left[i] = right[i] = i;
    }

    for (i=1; i<=n; i++)
    {
        while ( h[left[i]-1] >= h[i] )
            left[i] = left[left[i]-1];
    }
    for (i=n; i>0; i--)
    {
        while ( h[right[i]+1] >= h[i] )
            right[i] = right[right[i]+1];
    }

    max = 0;
    for (i=1; i<=n; i++)
    {
        temp = h[i] * (right[i] - left[i] + 1);
        if ( temp > max )
            max = temp;
    }

    printf("%I64d\n", max);
}

int main ()
{
    while ( Input() )
    {
        Solve();
    }

    return 0;
}

题目大意：

    给定一个时间期间n，电脑的价格c，以及电脑的维修费用m(y,z)（第y台电脑从y年用到第z年总的维修费用）。让你求出在期限n中使用电脑的最低费用。

思路：
    为了让总费用最低，你必须作出这样的决策：假设你正在使用某一台电脑已用到y年，你y+1年是继续用这台电脑，还是重新买第y+1台电脑（注意，这里的y+1是指输入中的第y+1行电脑，而不是指你已购买了y+1台电脑，因为y年只能买输入中的第y行电脑，为了不产生混淆，将电脑用编号表示）。显然，某一阶段的最优解并不能一定导致全局的最优解，所以肯定不能用贪心。
    我们从最后的情况来考虑，最后必然是某一个编号为y的电脑，从第y年使用到第n年，而前面的1～y-1年，自己只可能购买编号为1~y-1的电脑使用到y-1年。这样，问题的范围就减小了，从编号为1～n的电脑使用n年，降低到了编号为1～y-1的电脑使用y-1年。经分析，可推出递推式：
    F[n] = min { F[i] + c + m[i+1][n] | 0<=i<=n-1 }
F[n]表示n台电脑使用n年的最低费用

代码：

#include <cstdio>
#include <climits>
#include <cstring>

const int MAX = 1005;
int n, c;
int mend[MAX][MAX];
int f[MAX];
int cost;

bool Input ()
{
    if ( scanf("%d", &c) == EOF )
        return false;
    scanf("%d", &n);
    int i, j;
    for (i=1; i<=n; i++)
    {
        for (j=i; j<=n; j++)
            scanf("%d", &mend[i][j]);
    }
    return true;
}


void Solve ()
{
    int i, j;
    memset(f, 0, sizeof(f));
    for (i=1; i<=n; i++)
    {
        f[i] = INT_MAX;
        for (j=0; j<i; j++)
        {
            if ( f[j] + mend[j+1][i] + c < f[i] )
                f[i] = f[j] + mend[j+1][i] + c;
        }
    }
    printf("%d\n", f[n]);
}

int main ()
{
    while ( Input() )
    {
        Solve ();
    }

    return 0;
}

题意：
    就是有这样一个序列：1 12 123 1234 12345 .....，输入序列的下标，让你算出该序列所在下标的字符

思路：
    一开始想用字符串模拟来做，结果TLE。后来看了discuss，又想了一下，发现可以按规律将序列分成几段，然后再在每段中查找。具体做法是：先按序列 中数字的位数来分，112123...123456789是一段，1..10 1..11 1..12 ... 1..99是一段，1..100 ... 1..999是一段，以此类推。确定了是在上面的哪一段以后，再按类似的思想确定这个下标是在哪个12345...n的序列，最后判断是在其中哪个数字的 哪一位。

代码：
#include <iostream>
#include <cmath>
using namespace std;

const long long a[] = {0, 45, 9045, 1395495, 189414495, 2147483648};            //112123...9, 11231234...99, ... 的位数
const long long b[] = {1, 11, 192, 2893, 38894, 488895, 5888896};                //1, 1234...10, 1234...100, ...的位数

int digit (int n)
{
    int ans = 1;
    while ( n / 10 != 0 )
    {
          n /= 10;
          ans ++;
    }
    return ans;
}

char Pos (int n, long long index)      //在1234...n中找到下标为index的字符
{
     long long i, j;
     long long pos = 0;
     for (i=1; i<=n; i++)
     {
         pos += digit(i);
         if ( pos >= index )
            break;
     }
    
     pos -= digit(i);               //定位在i上
     j = digit(i) - (index - pos);
     //if ( j == digit(i) - 1 )
     //   cout<<endl;
     while ( j > 0 )
     {
           i /= 10;
           j --;
     }

     return (i % 10) + '0';
}


char Find (long long pos)
{
     long long p, t;
     int index = 0;
     int temp;
     while ( a[index] < pos )
     {
           index ++;
     }
     p = a[index - 1];
    
     p += b[index - 1];
     temp = int(pow(10.0, index-1));
     t = b[index - 1] + index;
     while ( p < pos )
     {
           p += t;
           t += index;
           temp ++;
     }
    
     p -= t - index;
    
     return Pos(temp, pos-p);
}

int main ()
{
    int test;
    long long i;
    cin>>test
    while ( test-- )
    {
          cin>>i;
          cout<<Find(i)<<endl;
    }

    return 0;

    一开始看还以为是一道博弈的题目，再仔细看才发现并不是博弈，也不是很难。大致意思是：有n堆石子，第i堆有Ki个石子，每轮一方可以从任意堆中取出一个或多个石子，所有石子都被取光时，游戏也结束了，那个最后一轮拿走石子的人就是胜利者。问你有多少种方法使对方处于必败的局面。题目并不难，是因为题目中已经告诉你了产生必败局面的条件：如果所有堆的石子数的异或和为0，那么处于此局面的人就必败。
    因为每次只能从一个堆中取石子，所以只要对于每个堆i，先求出其他所有堆的异或和temp，再看0～Ki-1与这个异或和再进行异或是否为0，只要为0就得到一种胜利的方法。自己先是想枚举0～Ki-1，与temp进行异或。后来感觉没有必要，只要Ki>temp就可以了，因为若从堆i中取出x个石子，Ki-x异或temp==0 <==> Ki-x==temp，只要Ki>temp，就存在Ki-x==temp。

#include <cstdio>

#define PILE 1001

__int64 stone[PILE], test;       //test为所有石子数的异或和
int piles;

bool Input ()
{
    scanf("%d", &piles);
    if ( piles == 0 )
        return false;
   
    int i;
    for (i=0; i<piles; i++)
        scanf("%I64d", &stone[i]);
    return true;
}

void Solve ()
{
    int i, ans;
    __int64 temp;
    test = 0;
    ans = 0;
    for (i=0; i<piles; i++)
        test ^= stone[i];
   
    if ( test != 0 )
    {
        for (i=0; i<piles; i++)
        {
            temp = test ^ stone[i];      //再与stone[i]做一次异或，相当于除stone[i]对其他所有堆的石子进行异或

            if ( stone[i] > temp )
                ans++;
        }
    }
    printf("%d\n", ans);
}

int main ()
{
    while ( Input() )
    {
        Solve();
    }
   
    return 0;
}

    地图上有一些beeper，让你从起点搜集所有beeper，再回到起点。但你只可以水平或者竖直的走，不能走对角线。让你找出这样走的最短路径长度。
    因为地图最大只有20×20，而beeper最多也只有10个，所以可以考虑用深搜，找到所有可能路径，在其中加一些简单的减枝就可以了。起初以为会超时，可最后还是0ms。：）

Source Code

Problem: 2907		User: QuXiao
Memory: 176K		Time: 0MS
Language: C++		Result: Accepted

• Source Code

#include <iostream>
#include <climits>
using namespace std;

struct Point
{
	int x, y;
};

int num, X, Y;
Point start, beeper[15];
int shortest;
int visited[15];


int Length (Point p1, Point p2)
{
	return abs(p1.x - p2.x) + abs(p1.y - p2.y);
}

void Input ()
{
	int i;
	cin>>X>>Y;
	cin>>start.x>>start.y;
	cin>>num;
	for (i=0; i<num; i++)
		cin>>beeper[i].x>>beeper[i].y;
}

void DFS (int cur, int len, int n)
{
	if ( n == num )
	{
		int t = Length(beeper[cur], start);
		if ( len +  t < shortest )
			shortest = len + t;
	}
	else if ( len < shortest )
	{
		int i;
		for (i=0; i<num; i++)
		{
			if ( visited[i] == 0 )
			{
				visited[i] = 1;
				DFS (i, len+Length(beeper[cur], beeper[i]), n+1);
				visited[i] = 0;
			}
		}
	}
}


void Solve ()
{
	int i, t;
	shortest = INT_MAX;
	memset(visited, 0, sizeof(visited));
	for (i=0; i<num; i++)
	{
		t = Length(beeper[i], start);
		visited[i] = 1;
		DFS (i, t, 1);
		visited[i] = 0;
	}
	cout<<"The shortest path has length "<<shortest<<endl;
}

int main ()
{
	int test;
	cin>>test;
	while ( test-- )
	{
		Input ();
		Solve ();
	}

	return 0;
}
    

    大家好，我对算法比较感兴趣。希望能借此平台，与我有同样爱好的朋友们能够多多交流，共同进步！