Senior Pan fails in his discrete math exam again. So he asks Master ZKC to give him graph theory problems everyday.
The task is simple : ZKC will give Pan a directed graph every time, and selects some nodes from that graph, you can calculate the minimum distance of every pair of nodes chosen in these nodes and now ZKC only cares about the minimum among them. That is still too hard for poor Pan, so he asks you for help.
Input
The first line contains one integer T, represents the number of Test Cases.1≤T≤5.Then T Test Cases, for each Test Cases, the first line contains two integers n,m representing the number of nodes and the number of edges.1≤n,m≤100000
Then m lines follow. Each line contains three integers xi,yi representing an edge, and vi representing its length.1≤xi,yi≤n,1≤vi≤100000
Then one line contains one integer K, the number of nodes that Master Dong selects out.1≤K≤n
The following line contains K unique integers ai, the nodes that Master Dong selects out.1≤ai≤n,ai!=aj
Output
For every Test Case, output one integer: the answer
Sample Input
1
5 6
1 2 1
2 3 3
3 1 3
2 5 1
2 4 2
4 3 1
3
1 3 5
Sample Output
Case #1: 2

题意： 有向图，k个点相互之间最短路的最小值。
思路：

1. 相互之间最短路，假设分组为(i,j){i,j 属于 集合k}，纯暴力分组的话要n方复杂度。
2. 考虑二进制优化，分为两组，一组作为源点集合，一组作为汇点集合。取到了汇点中的一个，说明这个值是这次分组所能得到的最小值，那就直接返回。源点就直接压入堆中。且k中的一组(i,j)一定满足有一位二进制不同，那么枚举二进制位，某一位相同的，就分入同一组。于是就枚举了所有组合（实际过程中由于是多源多汇的，复杂度会大大降低）

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

typedef long long ll;
const int maxn = 2e5 + 7;
const ll INF = 0x3f3f3f3f;
ll ans,tot;
ll vis[maxn],dis[maxn],mark[maxn];
ll to[maxn],head[maxn],nex[maxn],val[maxn];
ll a[maxn];

struct Node
{
    ll x,v;
    bool operator<(const Node&rhs)const
    {
        return v > rhs.v;
    }
};
priority_queue<Node>Q;

void add(int x,int y,int z)
{
    to[++tot] = y;
    val[tot] = z;
    nex[tot] = head[x];
    head[x] = tot;
}

ll dijkstra()
{
    while(!Q.empty())
    {
        Node now = Q.top();Q.pop();
        ll x = now.x,v = now.v;
        if(vis[x])continue;
        if(mark[x])return v;
        for(ll i = head[x];i;i = nex[i])
        {
            ll y = to[i],w = val[i];
            if(dis[y] > dis[x] + w)
            {
                dis[y] = dis[x] + w;
                Q.push(Node{y,dis[y]});
            }
        }
    }
    return INF;
}

int main()
{
    int T;scanf("%d",&T);
    int kase = 0;
    while(T--)
    {
        ans = INF;tot = 0;
        memset(head,0,sizeof(head));
        int n,m;scanf("%d%d",&n,&m);
        for(int i = 1;i <= m;i++)
        {
            int x,y,z;scanf("%d%d%d",&x,&y,&z);
            add(x,y,z);
        }
        
        int k;scanf("%d",&k);
        for(int i = 1;i <= k;i++)scanf("%lld",&a[i]);
        
        for(int i = 0;i <= 20;i++)
        {
            memset(vis,0,sizeof(vis));
            memset(mark,0,sizeof(mark));
            memset(dis,INF,sizeof(dis));
            while(!Q.empty())
                Q.pop();
            for(int j = 1;j <= k;j++)
            {
                if((1 << i) & a[j])
                {
                    mark[a[j]] = 1;//起点
                }
                else
                {
                    dis[a[j]] = 0;
                    Q.push(Node{a[j],0});
                }
            }
            ans = min(ans,dijkstra());
            
            memset(vis,0,sizeof(vis));
            memset(mark,0,sizeof(mark));
            memset(dis,INF,sizeof(dis));
            while(!Q.empty())
                Q.pop();
            for(int j = 1;j <= k;j++)
            {
                if((1 << i) & a[j])
                {
                    dis[a[j]] = 0;
                    Q.push(Node{a[j],0});
                }
                else
                {
                    mark[a[j]] = 1;
                }
            }
            ans = min(ans,dijkstra());
        }
        printf("Case #%d: %lld\n",++kase,ans);
    }
    return 0;
}