题目来源：Light OJ 1316 1316 - A Wedding Party

题意：和HDU 4284 差点儿相同 有一些商店 从起点到终点在走过尽量多商店的情况下求最短路

思路：首先预处理每两点之前的最短路 然后仅仅考虑那些商店 个数小于15嘛 就是TSP问题 状态压缩DP搞一下 状态压缩姿势不正确 有必要加强

#include <cstdio>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstring>

using namespace std;

const int maxn = 510;

const int maxm = 16;

const int INF = 999999999;

struct edge

{

    int u, v, w;

	edge(){}

	edge(int u, int v, int w): u(u), v(v), w(w) {}

};

struct HeapNode

{

    int u, dis;

    HeapNode(){};

    HeapNode(int u, int dis): u(u), dis(dis){};

    bool operator < (const HeapNode& rhs)const

    {

        return dis > rhs.dis;

    }

};

vector <edge> G[maxn];

int d[maxn][maxn];

int dp[1<<maxm][maxm];

bool vis[maxn];

int n, m, t;

int a[maxm];

void Dijkstra(int s)

{

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

   		d[s][i] = INF;

	d[s][s] = 0;

    memset(vis, false, sizeof(vis));

    priority_queue <HeapNode> Q;

    Q.push(HeapNode(s, 0));

    while(!Q.empty())

    {

        HeapNode x = Q.top();

        Q.pop();

        int u = x.u;

        if(vis[u])

            continue;

        vis[u] = true;

        for(int i = 0; i < G[u].size(); i++)

        {

            edge e = G[u][i];

            int v = e.v;

            if(d[s][v] > x.dis + e.w)

            {

                d[s][v] = x.dis + e.w;

                Q.push(HeapNode(v, d[s][v]));

            }

        }

    }

}

int get(int x)

{

	int ans = 0;

	while(x)

	{

		if(x&1)

			ans++;

		x >>= 1;

	}

	return ans;

}

int main()

{

	int T;

    int cas = 0;

    scanf("%d", &T);

    while(T--)

    {

    	scanf("%d %d %d", &n, &m, &t);

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

            G[i].clear();

        for(int i = 0; i < t; i++)

        {

        	int x;

        	scanf("%d", &x);

        	a[i] = x;

        }

        for(int i = 0; i < m; i++)

        {

            int u, v, w;

            scanf("%d %d %d", &u, &v, &w);

			G[u].push_back(edge(u, v, w));

        }

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

 	 		Dijkstra(i);

	  	for(int s = 0; s < (1<<t); s++)

   		{

			for(int i = 0; i < t; i++)

 			{

        		dp[s][i] = INF;

				if(!(s&(1<<i)))

        			continue;

        		if(s == (1<<i))

       			{

       				//if(s == 2 && i == 1)

       				//	printf("%d\n", d[0][a[i]]);

 					dp[s][i] = d[0][a[i]];

 					continue;

       			}

       			for(int j = 0; j < t; j++)

       			{

       				if((s&(1<<j)) && (i != j))

       				{

       					if(dp[s^(1<<i)][j] == INF)

       						continue;

    					if(d[a[j]][a[i]] == INF)

							continue;

						//if(s == 3 && i == 0)

						//	printf("%d %d %d %d\n", dp[s^(1<<i)][j], d[a[j]][a[i]], j, dp[2][1]);

       					dp[s][i] = min(dp[s^(1<<i)][j] + d[a[j]][a[i]], dp[s][i]);

       				}

       			}

        	}

        }

        //printf("222*%d\n", dp[3][0]);

        int x;

        int ans = INF, sum = 0;

        for(int s = 1; s < (1<<t); s++)

        {

        	for(int i = 0; i < t; i++)

        	{

				//if(s == (1<<i))

        		//	printf("***%d %d %d\n", dp[s][i], i, s);

				//printf("**%d %d %d %d\n", dp[s][i], s, i, dp[2][i]);

				if(dp[s][i] == INF || d[a[i]][n-1] == INF)

        			continue;

        		int temp = get(s);

        		if(sum < temp || sum == temp && ans > dp[s][i]+d[a[i]][n-1])

        		{

        			sum = temp;

        			ans = dp[s][i]+d[a[i]][n-1];

        			x = s;

        		}

        	}

        }

        if(sum == 0)

        {

            printf("Case %d: Impossible\n", ++cas);

            continue;

        }

		printf("Case %d: %d %d\n", ++cas, sum, ans);

    }

    return 0;

}