题目传送门：
P1529 [USACO2.4] 回家 Bessie Come Home - 洛谷 (luogu.com.cn)
前言：
这道题要求找出最先到达谷仓的母牛所在牧场及其走过的最短路径长度，解题的关键在于利用图论中的最短路径算法，还是比较简单的，下面为大家讲解题目思路。
#构建图：
1、输入处理：
从输入当中读取都的数量 P，以及每条道路连接的两个牧场标号和道路长度。
2、数据结构选择：
我们使用邻接表来表示图，我们在 C++的代码当中通过 unordered_map<char,vector<Edge>> 实现 Edge 结构体包含目标节点和边的权重。
##计算最短路径：
1、选择算法：
对于每个母牛所在的牧场，计算到谷仓的最短路径。这里我们使用 Dijkstra算法，它是一种贪心算法，适用于边权非负的图。
### Dijkstra 算法步骤：
1、初始化的距离：
将所有的节点到趣事的节点的距离设为无穷大，其实节点到自身的距离设为 0 。在 C++代码当中来记录距离。
2、优先队列：
使用优先队列来存储待处理的节点及其到起始节点的距离，优先队列按照距离从小到大排序。
3、节点扩展：
每次从优先队列中取出距离最小的节点，遍历其所有邻接节点。如果通过当前节点到达邻接节点的距离比一致的该邻接节点到起始节点的距离更小，则更新邻接节点的距离，并将其加入优先队列。
4、终止条件：
当优先排列为空的时候，所有的可达节点的最短的距离都以计算出来。
####找出最近的母牛：
1、遍历母牛所在的牧场：
遍历所有代表母牛所在牧场的节点。
2、比较距离：
对每个母牛所在的牧场，我们调用 Dijkstra 算法计算到谷仓的最短距离，记录距离最小的母牛所在的牧场标号及其最短距离。
#####代码：
#include <bits/stdc++.h>
using namespace std;// 定义边的结构体
struct E {char to;int weight;E(char t, int w) : to(t), weight(w) {}
};// 定义图的邻接表
using G = unordered_map<char, vector<E>>;// Dijkstra算法计算从start到Z的最短距离
int dijkstra(const G& graph, char start) {unordered_map<char, int> dist;for (const auto& entry : graph) {dist[entry.first] = numeric_limits<int>::max();}dist[start] = 0;priority_queue<pair<int, char>, vector<pair<int, char>>, greater<pair<int, char>>> pq;pq.push({0, start});while (!pq.empty()) {int c1 = pq.top().first;char c2 = pq.top().second;pq.pop();if (c1 > dist[c2]) {continue;}for (const E& edge : graph.at(c2)) {int n = c1 + edge.weight;if (n < dist[edge.to]) {dist[edge.to] = n;pq.push({n, edge.to});}}}return dist['Z'];
}int main() {int p;cin >> p;G g;for (int i = 0; i < p; ++i) {char from, to;int weight;cin >> from >> to >> weight;g[from].emplace_back(to, weight);g[to].emplace_back(from, weight);}char C;int D = numeric_limits<int>::max();for (const auto& entry : g) {if (entry.first >= 'A' && entry.first < 'Z') {int dist = dijkstra(g, entry.first);if (dist < D) {D = dist;C = entry.first;}}}cout << C << " " << D << endl;return 0;
}
