题目大意

题目链接
After World War X, a lot of cities have been seriously damaged, and we need to rebuild those cities. However, some materials needed can only be produced in certain places. So we need to transport these materials from city to city. For most of roads had been totally destroyed during the war, there might be no path between two cities, no circle exists as well.
Now, your task comes. After giving you the condition of the roads, we want to know if there exists a path between any two cities. If the answer is yes, output the shortest path between them.

Input

Input consists of multiple problem instances.For each instance, first line contains three integers n, m and c, 2<=n<=10000, 0<=m<10000, 1<=c<=1000000. n represents the number of cities numbered from 1 to n. Following m lines, each line has three integers i, j and k, represent a road between city i and city j, with length k. Last c lines, two integers i, j each line, indicates a query of city i and city j.

Output

For each problem instance, one line for each query. If no path between two cities, output “Not connected”, otherwise output the length of the shortest path between them.

Sample Input

1
2
3
4
5
6
5 3 2
1 3 2
2 4 3
5 2 3
1 4
4 5

Sample Output

1
2
Not connected
6

分析

在森林中求lca。
用并查集判断两个点是不是在同一棵树中。
用tarjan离线一直mle。。。无语了， 最后用的倍增才过的。
第一次遇到用时间换空间的题。。。

倍增ac代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

typedef unsigned long long ull;
typedef pair<int, int> P;
#define ms(a, b) memset((a), (b), sizeof(a))
const int N = (int)1e5 + 5;
const int INF = 0x3f3f3f3f;

inline int read() {
    int res = 0;bool f = 0;char ch = getchar();
    while (ch < '0' || ch > '9')  { if (ch == '-') f = 1; ch = getchar(); }
    while (ch <= '9' && ch >= '0') { res = (res << 3) + (res << 1) + ch - '0'; ch = getchar(); }
    return f ? (~ res + 1) : res;
}

struct edge{
	int u, v, w, ne;
}ed[N];

int head[N], dis[N], cnt, n, m;

int deep[N], fa[N][20];

inline void init(){
	ms(head, -1);
	cnt = 0;
	ms(deep, 0);
	ms(dis, 0);
}

inline void add(int u, int v, int w){
	ed[cnt] = {u, v, w, head[u]};
	head[u] = cnt++;
}

inline void dfs(int u, int pre){

	deep[u] = deep[pre] + 1; // deep数组表示深度
	fa[u][0] = pre;          // fa[i][j] 表示i的第2^j辈的祖先
	for (int i = 1; i < 20; ++i)
		fa[u][i] = fa[fa[u][i - 1]][i - 1];  
		// fa[i][j] = fa[fa[i][j - 1]][j - 1]  i的第2^j辈的祖先 等于 i的第2^(j-1)辈的祖先的第2^(j-1)辈的祖先
	for (int i = head[u]; ~i; i = ed[i].ne){
		int v = ed[i].v;
		if(v == pre) continue;
		dis[v] = dis[u] + ed[i].w;
		dfs(v, u);
	}
}

inline int lca(int a, int b){
	if (deep[a] < deep[b]) swap(a, b);
	// 运用二进制的思想 使得deep[a] == deep[b] 比如 7 可以用4 2 1表示
	for (int i = 19; i >= 0; --i)
		if (deep[a] - (1 << i) >= deep[b])
			a = fa[a][i];
	
	if (a == b) return a;
	// 倍增 2^k 步的爬, 找最小的满足 a != b 的
	for (int i = 19; i >= 0; --i){
		if (fa[a][i] != fa[b][i])
			a = fa[a][i], b = fa[b][i];
	}
	return fa[a][0];
}
int t, u, v, w;
int main(){
	t = read();
	while(t--){
		n = read(), m = read();
		init();
		for (int i = 1; i < n; ++i){
			u = read(), v = read(), w = read();
			add(u, v, w);
			add(v, u, w);
		}
		dfs(1, 0);
		while(m--){
			u = read(), v = read();
			int x = lca(u, v);
			printf("%d\n", dis[u] + dis[v] - 2 * dis[x]);
		}
	}
	return 0;
}

tarjan MLE代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
#include <map>
#include <set>
#include <ctime>
#include <cmath>
#include <queue>
#include <stack>
#include <bitset>
#include <cctype>
#include <cstdio>
#include <vector>
#include <utility>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

typedef unsigned long long ull;
typedef pair<int, int> P;
#define ms(a, b) memset((a), (b), sizeof(a))
const int N = (int)1e4 + 5;
const int M = (int)1e6 + 10;
const int INF = 0x3f3f3f3f;

inline int read() {
    int res = 0;bool f = 0;char ch = getchar();
    while (ch < '0' || ch > '9')  { if (ch == '-') f = 1; ch = getchar(); }
    while (ch <= '9' && ch >= '0') { res = (res << 3) + (res << 1) + ch - '0'; ch = getchar(); }
    return f ? (~ res + 1) : res;
}

struct edge {
    int u, v, w, ne;
}ed[N << 1], eq[M << 1]; // ed存边 eq离线存询问

int head[N], f[N], hq[N];
int dis[N], ans[N];
int vis[N];
int cnt, n, m, cnt1;

void init(){
    cnt = cnt1 = 0;
    for (int i = 0; i <= n; ++i){
        f[i] = i;
    }
    ms(head, -1);
    ms(hq, -1);
    ms(vis, 0);
    ms(ans, 0);
    ms(dis, -1);
}
inline void add(int &u, int &v, int &w){
    ed[cnt] = {u, v, w, head[u]};
    head[u] = cnt++;
}
inline void addq(int &u, int &v, int &id){
	eq[cnt1] = {u, v, id, hq[u]}; // 在结构体里虽然还是w， 但是咱们用它表示id
	hq[u] = cnt1++;
}


inline int tofind(int &x){
    return (f[x] == x) ? f[x] : (f[x] = tofind(f[x]));
}
inline void tojoin(int &a, int &b){
	a = tofind(a);
	b = tofind(b);
	if (a != b)
		f[b] = a;
}

void tarjan(int &u, int sgn){
	// 分为两部分， 第一部分 建树 第二部分 求ans
    // 第一部分， 建树
    vis[u] = sgn;
    for (int i = head[u]; ~i; i = ed[i].ne){
        int &v = ed[i].v, &w = ed[i].w;
        if (vis[v] == sgn) continue;
        dis[v] = dis[u] + w; // v到根结点的距离
        tarjan(v, sgn);
        f[v] = u; // 这里直接连上(f[v] = u)就行, 
    }

    for (int i = hq[u]; ~i; i = eq[i].ne){ // 与u相关的边
    	int &v = eq[i].v, &id = eq[i].w;
    	if (vis[v] != sgn + 1) continue; // 2 是以为这离线过了的点
    	
    	int lca = tofind(v);
        if (dis[v] != -1)
    	   ans[id] = dis[u] + dis[v] - 2 * dis[lca];
    	
    }
    vis[u] = sgn + 1;
}

int t, u, v, w;
int main(){
	int q;
	while(~scanf("%d%d%d", &n, &m, &q)){
		init(); // init 要放在n之后， 因为这个又被卡了好长时间。。。。。。
	    for (int i = 1; i <= m; ++i){
	    	u = read(), v = read(), w = read();
	        add(u, v, w);
	        add(v, u, w);
	      
	    }
	    
	    for (int i = 0; i < q; ++i){
	    	u = read(), v = read();
	        addq(u, v, i);
	        addq(v, u, i);
	    }
	    for (int i = 1; i <= n; ++i){
	    	if (!vis[i])
	    		tarjan(i, 2 * i);
	    }
	    for (int i = 0; i < q; ++i){
	    	if (!ans[i]) puts("Not connected");
	        else printf("%d\n", ans[i]);
	    }
	}
    return 0;
}
1
恰似你一低头的温柔，娇弱水莲花不胜寒风的娇羞， 我的心为你悸动不休。  --mingfuyan