【一本通】农场派对

💐The Begin💐点点关注，收藏不迷路💐

N头牛要去参加一场在编号为x(1≤x≤n)的牛的农场举行的派对(1≤N≤1000)，有M(1≤m≤100000)条有向道路，每条路长ti(1≤ti≤100)；每头牛都必须参加完派对后回到家，每头牛都会选择最短路径，求这n个牛的最短路径(一个来回)中最长的一条的长度。

特别提醒：可能有权值不同的重边

输入

第一行：N,M,X；

第二–m+1行：Ai,Bi,Ti，表示有一条从Ai到Bi的路，长度为Ti．

输出

最长最短路的长度。

样例输入

4 8 2
1 2 4
1 3 2
1 4 7
2 1 1
2 3 5
3 1 2
3 4 4
4 2 3

样例输出

10

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <climits>
using namespace std;const int MAX_N = 1000;
const int MAX_M = 100000;
const int INF = 0x3f3f3f3f;// 表示边的结构体，存储起点、终点和边的长度
struct Edge {int from;int to;int weight;
};// 图类，使用邻接表存储图，包含顶点数和邻接表数组
class Graph {
public:int numVertices;vector<Edge> adjLists[MAX_N];Graph(int numVertices) : numVertices(numVertices) {}// 向图中添加边（考虑重边情况，取较小权值的边）void addEdge(int from, int to, int weight) {Edge newEdge = {from, to, weight};for (auto& edge : adjLists[from]) {if (newEdge.weight < edge.weight) {  // 处理重边，取小权值边adjLists[from].insert(adjLists[from].begin(), newEdge);return;}}adjLists[from].push_back(newEdge);}
};// Dijkstra算法求单源最短路径，使用优先队列（小根堆）优化
void dijkstra(Graph& graph, int start, vector<int>& dist) {dist.assign(graph.numVertices, INF);dist[start] = 0;// 优先队列，存储pair类型，first是距离，second是节点编号，小根堆按照距离从小到大排序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();for (auto& edge : graph.adjLists[u]) {int v = edge.to;int weight = edge.weight;if (dist[v] > dist[u] + weight) {dist[v] = dist[u] + weight;pq.push({dist[v], v});}}}
}int main() {int n, m, x;cin >> n >> m >> x;  // 读入牛的数量、道路数量、派对举办地点Graph graph(n);  // 创建图对象for (int i = 0; i < m; i++) {int a, b, t;cin >> a >> b >> t;  // 读入每条道路的起点、终点、长度graph.addEdge(a - 1, b - 1, t);  // 向图中添加边（注意顶点编号减1转换为数组下标）}// 正向图从派对地点出发到各点的最短距离vector<int> distTo(n);dijkstra(graph, x - 1, distTo);// 反向图，将所有边反向，再求从各点到派对地点（原来的起点）的最短距离，相当于求从派对地点回到各点的最短距离Graph reverseGraph(n);for (int i = 0; i < n; i++) {for (auto& edge : graph.adjLists[i]) {reverseGraph.addEdge(edge.to, edge.from, edge.weight);}}vector<int> distBack(n);dijkstra(reverseGraph, x - 1, distBack);int maxRoundTrip = 0;for (int i = 0; i < n; i++) {maxRoundTrip = max(maxRoundTrip, distTo[i] + distBack[i]);}cout << maxRoundTrip << endl;return 0;
}

💐The End💐点点关注，收藏不迷路💐