HDU 6166 Senior Pan（k点中最小两点间距离）题解

题意：n个点，m条有向边，指定k个点，问你其中最近的两点距离为多少

思路：这题的思路很巧妙，如果我们直接枚举两点做最短路那就要做C（k，2）次。但是我们换个思路，我们把k个点按照二进制每一位的0和1分类logn次，然后做集合最短距离。因为任意两个不等的数，总有一位不一样，所以每个点都有机会和其他点在不同集合。那么这样就花了logn次枚举了所有情况。集合最短距离可以指定一个超级源点和超级汇点，然后做两点最短路。

代码：

#include<cmath>

#include<set>

#include<queue>

#include<cstdio>

#include<vector>

#include<cstring>

#include <iostream>

#include<algorithm>

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

const int maxn =  + ;

const ull seed = ;

const int INF = 0x3f3f3f3f;

const int MOD = ;

struct Edge{

    int to, w, next;

}edge[maxn * ];

struct node{

    int v, w;

    node(int _v = , int _w = ): v(_v), w(_w){}

    bool operator < (const node r) const{

        return w > r.w;

    }

};

int head[maxn], tot;

void addEdge(int u, int v, int w){

    edge[tot].w = w;

    edge[tot].to = v;

    edge[tot].next = head[u];

    head[u] = tot++;

}

int n, m, k;

int dis[maxn], q[maxn];

bool vis[maxn];

int dij(int s, int e){

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

    memset(dis, INF, sizeof(dis));

    priority_queue<node> Q;

    while(!Q.empty()) Q.pop();

    dis[s] = ;

    Q.push(node(s, ));

    node tmp;

    while(!Q.empty()){

        tmp = Q.top();

        Q.pop();

        int u = tmp.v;

        if(vis[u]) continue;

        vis[u] = true;

        for(int i = head[u]; i != -; i = edge[i].next){

            int v = edge[i].to;

            if(!vis[v] && dis[v] > dis[u] + edge[i].w){

                dis[v] = dis[u] + edge[i].w;

                Q.push(node(v, dis[v]));

            }

        }

    }

    return dis[e];

}

void init(){

    memset(head, -, sizeof(head));

    tot = ;

}

int a[maxn], b[maxn], w[maxn];

int main(){

    int T, ca = ;

    scanf("%d", &T);

    while(T--){

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

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

            scanf("%d%d%d", &a[i], &b[i], &w[i]);

        }

        scanf("%d", &k);

        for(int i = ; i <= k; i++){

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

        }

        int ans = INF, p = ;

        while(n >> p){

            init();

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

                addEdge(a[i], b[i], w[i]);

            for(int i = ; i <= k; i++){

                if((q[i] >> p) & ){

                    addEdge(, q[i], );

                }

                else{

                    addEdge(q[i], n + , );

                }

            }

            ans = min(ans, dij(, n + ));

            init();

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

                addEdge(a[i], b[i], w[i]);

            for(int i = ; i <= k; i++){

                if((q[i] >> p) & ){

                    addEdge(q[i], , );

                }

                else{

                    addEdge(n + , q[i], );

                }

            }

            ans = min(ans, dij(n + , ));

            p++;

        }

        printf("Case #%d: %d\n", ca++, ans);

    }

    return ;

}