𝐵B 头奶牛 (1≤𝐵≤25000)(1≤B≤25000)，有 𝑁(2×𝐵≤𝑁≤50000)N(2×B≤N≤50000) 个农场，编号 11 到 𝑁N，有 𝑀(𝑁−1≤𝑀≤100000)M(N−1≤M≤100000) 条双向边，第 𝑖i 条边连接农场 𝑅𝑖Ri 和 𝑆𝑖(1≤𝑅𝑖≤𝑁,1≤𝑆𝑖≤𝑁)Si(1≤Ri≤N,1≤Si≤N)，该边的长度是 𝐿𝑖(1≤𝐿𝑖≤2000)Li(1≤Li≤2000)。居住在农场 𝑃𝑖Pi 的奶牛 A (1≤𝑃𝑖≤𝑁)(1≤Pi≤N)，想送一份新年礼物给居住在农场 𝑄𝑖(1≤𝑄𝑖≤𝑁)Qi(1≤Qi≤N) 的奶牛 B，但是奶牛 A 必须先到大卫老师（居住在编号 11 的农场）那里取礼物，然后再送给奶牛 B。你的任务是：奶牛 A 至少需要走多远的路程？
输入格式
-
第一行三个整数 𝑁,𝑀,𝐵N,M,B。
-
第 22 至 𝑀+1M+1 行，每行 33 个整数 𝑅𝑖,𝑆𝑖,𝐿𝑖Ri,Si,Li。
-
第 𝑀+2M+2 至 𝑀+𝐵+1M+B+1 行，进行 𝐵B 次询问，每行 22 个整数 𝑃𝑖,𝑄𝑖Pi,Qi。
输出格式
每次询问输出一个整数，即答案。
输入输出样例
输入 #1复制
6 7 3 1 2 3 5 4 3 3 1 1 6 1 9 3 4 2 1 4 4 3 2 2 2 4 5 1 3 6
输出 #1复制
6 6 10
代码：
#include<bits/stdc++.h>
using namespace std;
struct Edge {int to;int weight;
};
class Graph {
public:int sum; // 农场的数量vector<vector<Edge>> ve; // 邻接表Graph(int n) {sum = n;ve.resize(n + 1);}void addEdge(int from, int to, int weight) {ve[from].push_back({to, weight});ve[to].push_back({from, weight});}int a(int start, int target) {vector<int> distance(sum + 1, INT_MAX);vector<bool> visited(sum + 1, false);distance[start] = 0;priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;pq.push({0, start});while (!pq.empty()) {int u = pq.top().second;pq.pop();if (visited[u]) {continue;}visited[u] = true;for (const auto& edge : ve[u]) {int v = edge.to;int weight = edge.weight;if (distance[u] + weight < distance[v]) {distance[v] = distance[u] + weight;pq.push({distance[v], v});}}}return distance[target];}
};int main() {int N, M, B;cin >> N >> M >> B;Graph graph(N);for (int i = 0; i < M; ++i) {int R, S, L;cin >> R >> S >> L;graph.addEdge(R, S, L);}for (int i = 0; i < B; ++i) {int P, Q;cin >> P >> Q;int dn = graph.a(P, 1) + graph.a(1, Q);cout << dn << endl;}return 0;
}
