原题链接：http://acm.hdu.edu.cn/showproblem.php?pid=2586
题意：n个点，编号1-n，接下来n-1行，每行三个数字表示两点之间的距离，题目是保证两点间不会出现两条可行的路，也就是不会有环；m条询问，每条询问两个数字a，b表示a，b的最短距离。
#define _CRT_SECURE_NO_DEPRECATE #include<iostream> #include<vector> #include<cstring> #include<queue> #include<stack> #include<algorithm> #include<cmath> #define INF 99999999 #define eps 0.0001 using namespace std; struct Edge { int w; int v; int next; }; int t; int n, m; int cnt; Edge edge[40005 * 2]; int head[40005]; int x[40005]; int y[40005]; int z[40005]; int pre[40005]; int dist[40005]; bool vis[40005]; void add(int u, int v, int w) { edge[cnt].w = w; edge[cnt].v = v; edge[cnt].next = head[u]; head[u] = cnt++; edge[cnt].w = w; edge[cnt].v = u; edge[cnt].next = head[v]; head[v] = cnt++; } int find(int x) { if (pre[x] != x) return pre[x] = find(pre[x]); return x; } void tarjan(int u) { vis[u] = 1; pre[u] = u; for (int i = 0; i < m; i++) { if (x[i] == u&&vis[y[i]]) z[i] = find(y[i]); if (y[i] == u&&vis[x[i]]) z[i] = find(x[i]); } for (int i = head[u]; i != -1; i = edge[i].next) { int v = edge[i].v; if (!vis[v]) { dist[v] = dist[u] + edge[i].w; tarjan(v); pre[v] = u; } } } int main() { scanf("%d", &t); while (t--) { scanf("%d%d", &n, &m); int u, v, w; cnt = 0; memset(head, -1, sizeof(head)); for (int i = 1; i < n; i++) { scanf("%d%d%d", &u, &v, &w); add(u, v, w); } for (int i = 0; i < m; i++) { scanf("%d%d", &u, &v); x[i] = u; y[i] = v; } memset(vis, 0, sizeof(vis)); dist[1] = 0; tarjan(1); for (int i = 0; i < m; i++) printf("%d\n", dist[x[i]] + dist[y[i]] - 2 * dist[z[i]]); } return 0; }
