题目地址：HDUOJ：Problem – 6166

题目描述

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.
给定一个n个点m条边的有向带权图，其中有k个特殊点，求这k个特殊点之间两两最短路的最小值。

输入输出格式

输入格式：
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

输出格式：
For every Test Case, output one integer: the answer

输入输出样例

输入样例#1：

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

输出样例#1：

Case #1: 2

题解

首先多源最短路Dijkstra是可以做的，但是这里并不是起点集合到终点集合，而是直接给你扔一个点集来求。如果暴力地算，k一大就GG了。我们需要一种划分手段，减少求最短路的次数。
这里要提到一种技巧，叫二进制划分。指的是对于二进制的每一位是0还是1进行集合划分。例如本题，点的编号最大为100000，不会超过20位二进制，那么我们对于20位二进制每一位都划分一次，这样最短路的计算次数就减少为20次了。这样做的复杂度只会在Dijkstra的复杂度上乘一个\log n，是可以接受的。
为什么把所有划分跑完最短路后就能得到答案呢？因为点的编号都不相同，那么二进制至少有一位不相同，可以保证任意两个点在某一次划分中被分开了。这也就是说，我们相当于把每两点之间的最短路都计算了一遍。
需要注意的是，由于是有向图，0集合到1集合跑一遍，反过来还要跑一遍。

代码

// Code by KSkun, 2018/3
#include <cstdio>
#include <cstring>

#include <vector>
#include <algorithm>
#include <queue>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    char c = fgc();
    while(c < '0' || c > '9') {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(c >= '0' && c <= '9') {
        res = res * 10 + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int MAXN = 100005;
const LL INF = 0x3f3f3f3f3f3f3f3fll;

int T, n, m, ut, vt, wt, k, a[MAXN];
LL dis[MAXN];
bool vis[MAXN], goal[MAXN];

struct Edge {
    int to;
    LL w;
};

struct Node {
    int u;
    LL d;
    bool operator<(const Node &rhs) const {
        return d > rhs.d;
    }
};

std::vector<Edge> gra[MAXN];
std::vector<int> v0, v1;
std::priority_queue<Node> pq;

inline LL dijkstra(std::vector<int> st) {
    while(!pq.empty()) pq.pop();
    memset(vis, 0, sizeof(vis));
    memset(dis, 0x3f, sizeof(dis));
    for(int i = 0; i < st.size(); i++) {
        int u = st[i];
        dis[u] = 0;
        pq.push(Node {u, 0});
    }
    while(!pq.empty()) {
        int u = pq.top().u; LL d = pq.top().d; pq.pop();
        if(goal[u]) return d;
        if(vis[u]) continue;
        vis[u] = true;
        for(int i = 0; i < gra[u].size(); i++) {
            int v = gra[u][i].to, w = gra[u][i].w;
            if(!vis[v] && dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                pq.push(Node {v, dis[v]});
            }
        }
    }
    return INF;
}

int main() {
    T = readint();
    for(int kase = 1; kase <= T; kase++) {
        n = readint(); m = readint();
        for(int i = 1; i <= n; i++) {
            gra[i].clear();
        }
        for(int i = 1; i <= m; i++) {
            ut = readint(); vt = readint(); wt = readint();
            gra[ut].push_back(Edge {vt, wt});
        }
        k = readint();
        for(int i = 1; i <= k; i++) {
            a[i] = readint();
        }
        LL ans = INF;
        for(int i = 0; i < 20; i++) {
            v0.clear(); v1.clear();
            // v0 to v1 shortest path
            memset(goal, 0, sizeof(goal));
            for(int j = 1; j <= k; j++) {
                int u = a[j];
                if(u & (1 << i)) {
                    v1.push_back(u);
                } else {
                    v0.push_back(u);
                    goal[u] = true;
                }
            }
            ans = std::min(ans, dijkstra(v1));
            // v1 to v0 shortest path
            memset(goal, 0, sizeof(goal));
            for(int j = 0; j < v1.size(); j++) {
                goal[v1[j]] = true;
            }
            ans = std::min(ans, dijkstra(v0));
        }
        printf("Case #%d: %lld\n", kase, ans);
    }
    return 0;
}