信息学奥赛一本通在线题库 农场派对题解

题目需要求求出来去的路径中的最短路径的最大值，那就写一个Dijkstra算法，然后每到一个点求出起点到终点的最短路径距离加上终点到起点的最短路径的距离，然后找到最大的就是答案了。（在写Dijkstra的时候用了堆优化的优先队列，没有的话可能会TLE）
时间复杂度：没有堆优化的情况下使O（n ^ 2），堆优化：O（nlogn）

#include <iostream>
#include <cstdio>
#include <map>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;
typedef pair<int, int> p;
const int maxn = 1010;
const int inf = 0x3f3f3f3f;
vector<p > v[maxn];
int Dijkstra(int st, int ed) {
    priority_queue<p, vector<p >, greater<p> > q;
    int d[maxn];
    memset(d, inf, sizeof(d));
    d[st] = 0;
    q.push(make_pair(0, st));
    while (!q.empty()) {
        int now = q.top().second;
        q.pop();
        for (int i = 0; i < v[now].size(); i++) {
            int x = v[now][i].first;
            if (d[x] > d[now] + v[now][i].second) {
                d[x] = d[now] + v[now][i].second;
                q.push(make_pair(d[x], x));
            }
        }
    }
    if (d[ed] != inf) return d[ed];
    else return 0;
}
int main() {
    int n, m, x, Max = 0;
    scanf("%d %d %d", &n, &m, &x);
    for (int i = 0; i < m; i++) {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        v[a].push_back(make_pair(b, c));
    }
    for (int i = 1; i <= n; i++) {
        int ans = Dijkstra(i, x) + Dijkstra(x, i);
        Max = max(Max, ans);
    }
    printf("%d", Max);
    return 0;
}