题目大意：给出N个点。M条线，Q个询问，询问的是两点之间的最短距离
解题思路：恶心的数据量，一不小心就超空间了
这题给图不是张连通图，是森林，所以计算两点之间的最短距离时还要考虑一下是否在同一棵树中剩下的就是裸LCA了
#include#include #define N 10010#define M 20010#define C 2000010struct Edge{ int to, next, dis;}E[M];struct Edge2{ int to, next, w;}E2[C];int n, m, c, tot, tot2;int head[N], head2[N], dist[N], f[N], vis[N];void AddEdge(int u, int v, int dis) { E[tot].to = v; E[tot].next = head[u]; E[tot].dis = dis; head[u] = tot++; u = u ^ v; v = u ^ v; u = u ^ v; E[tot].to = v; E[tot].next = head[u]; E[tot].dis = dis; head[u] = tot++;}void AddEdge2(int u, int v) { E2[tot2].to = v; E2[tot2].next = head2[u]; E2[tot2].w = -1; head2[u] = tot2++; u = u ^ v; v = u ^ v; u = u ^ v; E2[tot2].to = v; E2[tot2].next = head2[u]; E2[tot2].w = -1; head2[u] = tot2++;}void init() { memset(head, -1, sizeof(head)); memset(head2, -1, sizeof(head2)); tot = tot2 = 0; int u, v, d; for (int i = 0; i < m; i++) { scanf("%d%d%d", &u, &v, &d); AddEdge(u, v, d); } for (int i = 0; i < c; i++) { scanf("%d%d", &u, &v); AddEdge2(u, v); } memset(vis, 0, sizeof(vis));}int find(int x) { return x == f[x] ? x : f[x] = find(f[x]);}void tarjan(int u, int time) { vis[u] = time; f[u] = u; int v; for (int i = head[u]; i != -1; i = E[i].next) { v = E[i].to; if (vis[v]) continue; dist[v] = dist[u] + E[i].dis; tarjan(v, time); f[v] = u; } for (int i = head2[u]; i != -1; i = E2[i].next) { v = E2[i].to; if (vis[v] == time) E2[i].w = E2[i^1].w = dist[u] + dist[v] - 2 * dist[find(v)]; }}void solve() { int cnt = 1; for (int i = 1; i <= n; i++) { if (!vis[i]) { dist[i] = 0; tarjan(i, cnt); } cnt++; } for (int i = 0; i < tot2; i += 2) { if (E2[i].w == -1) printf("Not connected\n"); else printf("%d\n", E2[i].w); }}int main() { while (scanf("%d%d%d", &n, &m, &c) != EOF) { init(); solve(); } return 0;}