Senior Pan（最短路+二進制分組）

題目連結

Problem Description

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

題目大意

有一個 n 個點 m 條邊的有向帶邊權圖。現在給你 k 個點，問 k 個點中最近的點對距離。

分析

可以先将這 k 個點用二進制來進行分組，點 i 和點 j 的下标分别是 i 和 j，由于 i 不等于 j，是以 i 和 j 的二進制表達式中，一定有一位不同。那麼，我們隻要劃分 log n 次，每次依據下标的二進制中第 i 位是 0 還是 1，分成兩個集合，然後再跑最短路就可以了。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int inf = 0x3f3f3f3f;
const int maxn = 1e5 + 10;
ll t, n, m, k, ans;
ll a[maxn], dis[maxn], vis[maxn], flag[maxn];

struct node{
	ll v, len;
};

vector<node> f[maxn << 1];

ll dijkstra()
{
	memset(dis, inf, sizeof(dis));
	memset(vis, 0, sizeof(vis));
	priority_queue<pii, vector<pii>, greater<pii> > q;
	for(int i = 1; i <= n; i++){
		if(flag[i] == 1){
			q.push({0, i});
			dis[i] = 0;
		}
	}
	while(!q.empty()){
		pii p = q.top();
		q.pop();
		int u = p.second;
		if(flag[u] == 2)
			return p.first;
		if(vis[u])
			continue;
		vis[u] = 1;
		for(int i = 0; i < f[u].size(); i++){
			node t = f[u][i];
			if(dis[t.v] > dis[u] + t.len){
				dis[t.v] = dis[u] + t.len;
				q.push({dis[t.v], t.v});
			}
		}
	}
	return inf;
}

void solve()	// 二進制分組 
{
	memset(flag, 0,sizeof(flag));
	ans = inf;
	for(int i = 1; i <= 17; i++){
		int bit = (1 << (i - 1));
		for(int j = 1; j <= k; j++){
			if(a[j] & bit)
				flag[a[j]] = 1;
			else
				flag[a[j]] = 2;
		}
		ans = min(ans, dijkstra());
		for(int j = 1; j <= n; j++){
			if(flag[j] == 1)
				flag[j] = 2;
			else if(flag[j] == 2)
				flag[j] = 1;
		}
		ans = min(ans, dijkstra());
	}
}

int main()
{
	cin >> t;
	for(int i = 1; i <= t; i++){
		cin >> n >> m;
		for(int j = 0; j <= n; j++)
			f[j].clear();
		for(int j = 0; j < m; j++){
			int x, y, z;
			cin >> x >> y >> z;
			f[x].push_back({y, z});
		}
		cin >> k;
		for(int j = 1; j <= k; j++)
			cin >> a[j];
		solve();
		printf("Case #%d: %lld\n", i, ans);
	}
	return 0;
}