题意分析

1.问题背景：

Farmer John 的奶牛拒绝参加他组织的马拉松比赛，因为他选择的路径对于奶牛们悠闲的生活方式来说太长了。 Farmer John 因此希望找到一条更合理的路径。 输入数据与“Navigation Nightmare”问题相同，描述了农场之间的连接关系。 随后给出一个整数 K，表示有 K 个距离查询。 每个查询给出两个农场的编号，要求计算这两个农场之间的最短路径距离（即沿路径上所有道路的长度之和）。

2.输入格式：

农场连接关系： 前 M+1 行描述了农场的连接关系。 每行包含四个部分：两个农场的编号、连接这两个农场的道路长度，以及一个方向字符（方向字符可以忽略，因为距离计算只与道路长度有关）。 例如：1 6 13 E 表示农场 1 和农场 6 之间有一条长度为 13 的道路，方向为 E（东）。 查询数量： 第 2+M 行是一个整数 K，表示距离查询的数量。 1 ≤ K ≤ 10,000。 距离查询： 接下来的 K 行，每行包含两个农场的编号，表示需要计算这两个农场之间的距离。 输出格式：

对于每个查询，输出两个农场之间的最短路径距离，每个结果占一行。

解题思路

1.问题建模：

这是一个典型的图论问题，涉及无向无环图（或森林）中的最短路径计算。 由于题目中提到$Navigation Nightmare$的输入格式，可以假设农场之间的连接关系构成一个无向无环图（即森林）。 需要处理多个查询，每个查询要求计算两个节点之间的最短路径距离。

2.算法选择：

对于无权图（或所有边权重相同），可以使用广度优先搜索（BFS）来找到最短路径。 对于有权图（边权重不同），可以使用 Dijkstra 算法来找到最短路径。 由于题目中边的权重是正数（道路长度），且需要处理多个查询，可以考虑使用离线处理的方法。

3.离线处理方法：

构建图： 首先读取所有农场的连接关系，构建图的邻接表表示。 邻接表是一种常用的图表示方法，可以高效地存储和遍历图的边。 处理查询： 将所有查询存储起来，然后对每个查询使用 Dijkstra 算法计算两个农场之间的距离。 由于查询数量较多$（K ≤ 10,000）$，且农场数量较大$（N ≤ 100,000）$，需要确保算法的时间复杂度是可接受的。 $Dijkstra$ 算法的时间复杂度为 $O(M + N log N)$，其中 M 是边的数量，N 是节点数量。

代码实现

#include <iostream>
#include <cstring>
#include <cstdio>  // 添加缺失的头文件

using namespace std;

const int maxn = 100005;

int p[maxn];
int head[maxn];
int qhead[maxn];

struct Node
{
	int to;
	int next;
	int w;
	int lca;
};

int m, n;
bool vis[maxn];
Node edge[maxn];
Node qedge[maxn];
int cnt;
int qcnt;
int dist[maxn];

void init()
{
	memset(p, 0, sizeof(p));
	memset(vis, false, sizeof(vis));
	memset(head, -1, sizeof(head));
	memset(qhead, -1, sizeof(qhead));
	memset(edge, 0, sizeof(edge));
	memset(dist, 0, sizeof(dist));
	cnt = 0;
	qcnt = 0;
}

void addEdge(int u, int v, int w)
{
	edge[cnt].w = w;
	edge[cnt].to = v;
	edge[cnt].next = head[u];
	head[u] = cnt++;
}

void addQEdge(int u, int v)
{
	qedge[qcnt].to = v;
	qedge[qcnt].next = qhead[u];
	qhead[u] = qcnt++;
}

int find(int x)
{
	if (p[x] != x)
		p[x] = find(p[x]);
	return p[x];
}

void lca(int u)
{
	p[u] = u;
	vis[u] = true;
	for (int k = head[u]; k != -1; k = edge[k].next)
	{
		if (!vis[edge[k].to])
		{
			dist[edge[k].to] = dist[u] + edge[k].w; // 更新和根结点的距离
			lca(edge[k].to);
			p[edge[k].to] = u;
		}
	}
	for (int k = qhead[u]; k != -1; k = qedge[k].next)
	{
		if (vis[qedge[k].to])
		{
			qedge[k].w = dist[u] + dist[qedge[k].to] - 2 * dist[find(qedge[k].to)]; // u和根结点的距离 + qedge[k].to与根结点的距离 - 2 * 公共祖先和根结点的距离
			qedge[k ^ 1].w = qedge[k].w;
			qedge[k].lca = find(qedge[k].to);
			qedge[k ^ 1].lca = qedge[k].lca;
		}
	}
}

int main()
{
	char c[2];
	while (scanf("%d%d", &n, &m) != EOF)
	{
		int num1, num2, length;
		int que;
		init();
		for (int i = 0; i < m; i++)
		{
			scanf("%d%d%d%s", &num1, &num2, &length, c);
			addEdge(num1, num2, length);
			addEdge(num2, num1, length);
		}
		scanf("%d", &que);
		for (int i = 0; i < que; i++)
		{
			scanf("%d%d", &num1, &num2);
			addQEdge(num1, num2);
			addQEdge(num2, num1);
		}
		for (int i = 1; i <= n; i++)
		{
			if (head[i] != -1)
			{
				lca(i);
				break;
			}
		}
		for (int i = 0; i < qcnt; i += 2)
		{
			printf("%d\n", qedge[i].w);
		}
	}
	return 0;
}