题目大意：给出N个点，M条线，Q个询问，询问的是两点之间的最短距离
解题思路：恶心的数据量，一不小心就超空间了 这题给图不是张连通图，是森林，所以计算两点之间的最短距离时还要考虑一下是否在同一棵树中
剩下的就是裸LCA了
struct 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(“, &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”);elseprintf(“%d\n”, E2[i].w);}}int main() {“, &n, &m, &c) != EOF) {init();solve();}return 0;}
，未经一番寒彻骨，焉得梅花扑鼻香
