Judges' response

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 565 Accepted Submission(s): 308


Problem Description 　　The contest is running and the judges is busy watching the progress of the contest. Suddenly, N - 1 (N <= 16) contestants hand up their hand at the same time. The judges should go to answer the contestants' question one by one. The judges already foresee that answering contest i's question would cost Ci minutes. In order to serve all the contestant, each judges is assigned to serve some subset of the contestants. As the judges have limited patience, each one of them can serve the contestants for no more than M minutes.
　　You are asked to solve two problems:
　　1. At least how many judges should be sent so that they can serve all the contestants? (Because the judges have limited patience, each one of them cannot serve too many contestants.)
　　2. If there are infinite number of judges, how to assign the route for each judge so that the sum of their walking time is minimized? Each contestant i is reside in place (xi, yi), the judges are in place (x1, y1). Assuming the walking speed of the judge is 1.

Input 　　There are several test cases, Each case begin with two integer N, M(with the meaning in the above context, 2 <= N <= 16, 0 <= M <= 100000).
　　Then N lines follow and line i will contain two numbers x, y(0 <= x, y <= 1000), indicating the coordinate of place i.
　　Then another N lines follow and line i will contain numbers Ci(0 <= Ci <= 1000), indicating the time to solve contestant i's question. C1 will 0 as place 1 is for the judges.
　　
　　The distance between place i and place j is defined as ceil(sqrt((xi - xj) ^ 2 + (yi - yj) ^ 2)). (ceil means rounding the number up, e.g. ceil(4.1) = 5)

Output 　　For each case, output two numbers. The first is the minimum number of judges for question 1. The second is the minimum sum of walking time for question 2.
　　If it's impossible to serve all the contestants, please output -1 -1 instead.

Sample Input

3 3
0 0
0 3
0 1
0
1
2

3 2
0 0
0 3
0 1
0
1
2

3 1
0 0
0 3
0 1
0
1
2
　　
16 35
30 40
37 52
49 49
52 64
31 62
52 33
42 41
52 41
57 58
62 42
42 57
27 68
43 67
58 48
58 27
37 69
0
19
30
16
23
11
31
15
28
8
8
7
14
6
19
11

Sample Output

1 6
2 8
-1 -1
8 467

Source 2012 ACM/ICPC Asia Regional Tianjin Online 题意：给出n个点，第一个点是裁判的位置，其余n-1个点是任务需要裁判去完成，每个裁判去完成任务总时间不能超过M（不包括走路的时间） ，每个点都有一个坐标和完成这个任务的时间，裁判从一个点到另一个时间所花的时间是两点之间的距离，（1）求完成所有任务最少需要多少个裁判。（2）如果有无数个裁判，要求完成所有的任务所经路程的时间总和最小是多少。（每个裁判最终要回到原来的位置，且最少用到条件（1）得到的裁判个数）。
分析：因为每个裁判做任务总时间不能超过M ，所以用状态压缩把一个裁判能完成的任务找出来，并且记录下来，那么接下来完成第（1）问就好办了，直接DP一下。要想做出第（2）问，那么首先要算出一个裁判去完成的任务状态（必须这种状态一个裁判能完成）的最少用时（不包括返回原来位置的用时），之后再把每个状态以某个点作为结尾点返回到裁判原来的位置的最少用时。再用一个分组背包求出用i 个裁判去完成任务状态 s 花的最少时间，最后就得出结果。

#include
#include

const int N = 1<<16 ;
const int inf= 0xfffffff ;

int dpk[N],dps[N],state[N],k,ok[N];
int map[16][16],routeDist[N][16],dpks[16][N];
double x[16],y[16];
int n,M,c[16];

//------------初始化-------------
void init()
{
    //求出两点之间这距离
    for(int i=0; ib?b:a;}
void countRouteDist()
{
    int tn=n-1;
    for(int i=1; i<(1<<>state[j]; s--) //每种任务的状态
        if((s|state[j])==s&&dpks[i-1][s^state[j]]!=inf)
            dpks[i][s]=min(dpks[i][s],dpks[i-1][s^state[j]]+dps[state[j]]);

}

void zeroOne()
{
    int tn=n-1;
    for(int i=0; i=state[i]; s--)
        if((s|state[i])==s)
        {
            if(dpk[s]>dpk[s^state[i]]+1)
                dpk[s]=dpk[s^state[i]]+1;
        }
}
int main()
{
    int flag,MIN;
    while(scanf("%d%d",&n,&M)>0)
    {
        flag=0;

        scanf("%lf%lf",&x[n-1],&y[n-1]);//裁判的位置
        for(int i=0; iM) flag=1;
        }

        if(flag)
        {
            printf("-1 -1\n"); continue;
        }

        init();
        zeroOne();
        countRouteDist();

        n--;
        MIN=inf;
        for(int i=dpk[(1<<>