【题意】大意就是一个人要从0点走到n－1点，路中有些点有商店可以买礼物，所以这个人想买多点礼物，但是又要尽快的走到n－1点，这两者之间呢，礼物的多少优先，其次是路程长度。

【分析】16个点显然是可以状压的，dp[sta][i]表示当前遍历的点的状态sta停留在shop[i]的最短路的估计值。这样状态首先是可以表示完全的，转移就显然很简单了。先预处理出每个商店到其他点的最短路径，以便后面的状态转移的需要。

【关键问题】最短路+TSP。

【最短路】这里最短路必须对n个点分别跑一遍，500个点，果断堆优化Dijstra!

【TSP】状压典型例题！dp[state][i]表示在i点，状态为state的最优答案。

【AC代码】一个巨长的ac代码，参考了别人的思路，花了两天写出并调试AC，还是太弱了~

#include <stdio.h>
#include <vector>
#include <queue>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <assert.h>
using namespace std;
const int maxn = 502;
const int maxm = 16;
const int inf = 0x3f3f3f3f;
struct edge{
   int u,v,w;
   edge(){}
   edge(int u,int v,int w):u(u),v(v),w(w){}
};
struct node{
   int u,dis;
   node(){}
   node(int u,int dis):u(u),dis(dis){}
   bool operator<(const node &x)const
   {
       return dis>x.dis;
   }
};
vector<edge>G[maxn];
int d[maxn][maxn];
int dp[1<<maxm][maxm];
int a[maxn];
int vis[maxn];
int n,m,t;
void Heap_Dijstra(int s)
{
    node cur;
    for(int i=0;i<=n;i++)d[s][i]=inf;
    memset(vis,false,sizeof(vis));
    d[s][s]=0;
    priority_queue<node>que;
    que.push(node(s,0));
    while(!que.empty())
    {
        cur=que.top();
        que.pop();
        int u=cur.u;
        if(vis[u])continue;
        vis[u]=true;
        for(int i=0;i<(int)G[u].size();i++)
        {
            edge temp=G[u][i];
            int v=temp.v;
            if(d[s][v]>cur.dis+temp.w)
            {
                d[s][v]=cur.dis+temp.w;
                que.push(node(v,d[s][v]));
            }
        }
    }
}
int get_num(int x)
{
    int ans=0;
    while(x)
    {
        if(x&1)ans++;
        x>>=1;
    }
    return ans;
}

int main()
{
    int T,cas=1;
    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++)
        {
            scanf("%d",&a[i]);//where shop is !
        }
        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++)
        {
            Heap_Dijstra(i);
        }
        //TSP.
        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)){
                    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;
                        dp[s][i]=min(dp[s^(1<<i)][j]+d[a[j]][a[i]],dp[s][i]);
                    }
                }
            }
        }
        //Find answer !
        int ans=inf,sum=0;
        for(int s=0;s<(1<<t);s++)
        {
            for(int i=0;i<t;i++)
            {
                if(dp[s][i]==inf||d[a[i]][n-1]==inf)continue;
                int temp=get_num(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];
                }
            }
        }
        printf("Case %d: ",cas++);
        if(sum==0)
            puts("Impossible");
        else
            printf("%d %d\n",sum,ans);
    }
    return 0;
}