题目描述

N
头牛要去参加在某农场举行的一场编号为 X
的牛的派对。

有 M
条有向道路，每条路长 Ti
；每头牛参加完派对后都必须回到家，每头牛都会选择最短路径。

求这 N
头牛的最短路径（一个来回）中最长的一条的长度。

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

输入格式
第一行包含三个整数 N,M,X
。

接下来 M
行，每行包含三个整数 Ai,Bi,Ti
，表示有一条从 Ai
到 Bi
的路，长度为 Ti
。

输出格式
共一行，一个数，表示最短路中最长的一条的长度。

数据范围
1≤N≤1000
,
1≤X≤N
,
1≤M≤105
,
1≤Ti≤100

样例

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

正反建图

(Dijkstra + 堆优化 + vector存图)

正反建图跑Dijkstra
不习惯写前向星，翻了半天都没找到vector的堆优化
补上代码:

C++ 代码

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int N = 1e5 + 10;
const int INF = 0x3f3f3f3f; // 定义一个常量表示无穷大
int dis[N];     //正向距离
int udis[N];    //反向距离
bool st[N];     //正向状态
bool ust[N];    //反向状态
int n, m ,x;
vector<pair<int, int>> e[N];
vector<pair<int, int>> ue[N];   //反向图
void dijkstra(int star) {
    memset(dis, INF, sizeof dis);  // 初始化所有距离为无穷大
    dis[star] = 0;  // 起点star到自己的距离为0
    priority_queue<pii, vector<pii>, greater<pii>> q; // 创建一个小根堆
    q.push({0, star}); // first表示距离，second表示路径

    while (q.size()) {
        int u = q.top().second; // 取出当前最小路径的节点
        q.pop();
        if (st[u]) continue; // 如果节点 u 已经处理过，跳过
        st[u] = true; // 标记节点 u 为已处理

        for (int i = 0; i < e[u].size(); i++) {
            int s = e[u][i].first;  // 目标节点
            int w = e[u][i].second; // 边的权值
            if (dis[u] + w < dis[s]) { // 松弛操作
                dis[s] = dis[u] + w;
                q.push({dis[s], s}); // 将更新后的节点和距离推入队列
            }
        }
    }
}

void udijkstra(int star) {
    memset(udis, INF, sizeof udis);  // 初始化所有距离为无穷大
    udis[star] = 0;  // 起点star到自己的距离为0
    priority_queue<pii, vector<pii>, greater<pii>> q; // 创建一个小根堆
    q.push({0, star}); // first表示距离，second表示路径

    while (q.size()) {
        int u = q.top().second; // 取出当前最小路径的节点
        q.pop();
        if (ust[u]) continue; // 如果节点 u 已经处理过，跳过
        ust[u] = true; // 标记节点 u 为已处理

        for (int i = 0; i < ue[u].size(); i++) {
            int s = ue[u][i].first;  // 目标节点
            int w = ue[u][i].second; // 边的权值
            if (udis[u] + w < udis[s]) { // 松弛操作
                udis[s] = udis[u] + w;
                q.push({udis[s], s}); // 将更新后的节点和距离推入队列
            }
        }
    }
}
int main() {
    cin >> n >> m >> x;
    while(m--)
    {
        int u, v, w;
        cin >> u >> v >> w;
        e[u].push_back({v, w});  // 由于是有向图，边只会添加从 u 到 v
        ue[v].push_back({u,w}); 
    }


    dijkstra(x);
    udijkstra(x);
    int res = 0;
    for(int i = 1; i <= n;i++)
    {
        if(dis[n] != INF && udis[n] != INF)
        res = max(res,dis[i] + udis[i]);
    }

    cout << res;
}