题目大意
「GXOI / GZOI 2019」旅行者（Luogu 5304）
给定一个有 $n$ 个结点，$m$ 条边的带权有向图和 $k$ 个关键点，求 $k$ 个点两两之间最短路长度的最小值。
$n \le 10^5, m \le 5 \times 10^5$。
思路分析
算法一
将关键点的编号转化为二进制。发现如果两个数不同，那么它们二进制位至少有一位不同。那么对于每一个二进制位计算这位为 $0$ 的点到这位为 $1$ 的点的最短路，最后再取最小值即可。
时间复杂度 $O(n \log^2 n)$。
算法二
对原图和反图做多源最短路，对于图上每个点染色，得到每个关键点的控制范围。然后对于每条边如果它两端的结点颜色不同则拿经过它的这条路径的长度来更新答案。
时间复杂度 $O(n \log n)$。
代码实现
使用方法二实现。
1 | |
2 | |
3 | |
4 | |
5 | using namespace std; |
6 | |
7 | typedef long long ll; |
8 | typedef pair<ll, int> P; |
9 | const int maxn = 1e5, maxm = 5e5; |
10 | const ll inf = ll(1e18 + .5) + 1; |
11 | int T, n, m, k, a[maxn + 3], u[maxm + 3], v[maxm + 3], w[maxm + 3], col[2][maxn + 3]; |
12 | int tot, ter[maxm + 3], wei[maxm + 3], nxt[maxm + 3], lnk[maxn + 3]; |
13 | ll dist[2][maxn + 3]; |
14 | priority_queue<P> H; |
15 | bool vis[maxn + 3]; |
16 | |
17 | void add(int u, int v, int w) { |
18 | ter[++tot] = v, wei[tot] = w; |
19 | nxt[tot] = lnk[u], lnk[u] = tot; |
20 | } |
21 | |
22 | void dijkstra(int t) { |
23 | for (int i = 1; i <= n; i++) { |
24 | dist[t][i] = inf, col[t][i] = 0, vis[i] = false; |
25 | } |
26 | for (int i = 1; i <= k; i++) { |
27 | dist[t][a[i]] = 0, col[t][a[i]] = a[i]; |
28 | H.push(P(0ll, a[i])); |
29 | } |
30 | while (!H.empty()) { |
31 | int u = H.top().second; |
32 | H.pop(); |
33 | if (vis[u]) continue; |
34 | vis[u] = true; |
35 | for (int i = lnk[u], v, w; i; i = nxt[i]) { |
36 | v = ter[i], w = wei[i]; |
37 | if (dist[t][u] + w < dist[t][v]) { |
38 | dist[t][v] = dist[t][u] + w, col[t][v] = col[t][u]; |
39 | H.push(P(-dist[t][v], v)); |
40 | } |
41 | } |
42 | } |
43 | } |
44 | |
45 | int main() { |
46 | scanf("%d", &T); |
47 | while (T--) { |
48 | scanf("%d %d %d", &n, &m, &k); |
49 | for (int i = 1; i <= m; i++) { |
50 | scanf("%d %d %d", &u[i], &v[i], &w[i]); |
51 | } |
52 | for (int i = 1; i <= k; i++) { |
53 | scanf("%d", &a[i]); |
54 | } |
55 | for (int t = 0; t < 2; t++) { |
56 | tot = 0; |
57 | for (int i = 1; i <= n; i++) { |
58 | lnk[i] = 0; |
59 | } |
60 | for (int i = 1; i <= m; i++) { |
61 | if (!t) add(u[i], v[i], w[i]); |
62 | else add(v[i], u[i], w[i]); |
63 | } |
64 | dijkstra(t); |
65 | } |
66 | ll ans = inf; |
67 | for (int i = 1; i <= m; i++) { |
68 | if (col[0][u[i]] && col[1][v[i]] && col[0][u[i]] != col[1][v[i]]) { |
69 | ans = min(ans, dist[0][u[i]] + dist[1][v[i]] + w[i]); |
70 | } |
71 | } |
72 | printf("%lld\n", ans); |
73 | } |
74 | return 0; |
75 | } |