結果

問題 No.3113 The farthest point
ユーザー mencotton
提出日時 2025-04-19 15:45:16
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,988 bytes
コンパイル時間 1,187 ms
コンパイル使用メモリ 83,140 KB
実行使用メモリ 21,696 KB
最終ジャッジ日時 2025-04-19 15:45:25
合計ジャッジ時間 7,692 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 20 WA * 13
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <cassert>
#include <queue>

using namespace std;
using ll = long long;
using ld = long double;

constexpr int INF = (1 << 30) - 10;
constexpr ll LINF = 1LL << 60;

inline void output_YesNo(bool x) { cout << (x ? "Yes" : "No") << endl; }

template<typename T>
inline void chmax(T &lhs, const T &rhs) { lhs = max(lhs, rhs); }

template<typename T>
inline void chmin(T &lhs, const T &rhs) { lhs = min(lhs, rhs); }

struct edge {
    int to;
    ll cost;
};

struct status {
    ll value;
    int prev;
    int now;

    bool operator<(const status &rhs) const { return value < rhs.value; };
    bool operator>(const status &rhs) const { return value > rhs.value; };
};

vector<ll> dijkstra(const int s, const vector<vector<edge> > &graph) {
    priority_queue<status, vector<status>, greater<> > que;
    vector<ll> dis(graph.size(), LINF);
    dis[s] = 0;
    que.push({0, -1, s});

    while (!que.empty()) {
        const auto [value, prev, v] = que.top();
        que.pop();

        if (dis[v] < value)continue;

        for (const auto [to, cost]: graph[v]) {
            if (to == prev) continue;

            if (dis[to] > value + cost) {
                dis[to] = value + cost;
                que.push({dis[to], v, to});
            }
        }
    }

    return dis;
}

int main() {
    int n;
    cin >> n;
    vector<vector<edge> > graph(n);
    for (int i = 0; i < n - 1; i++) {
        int from, to, cost;
        cin >> from >> to >> cost;
        from--, to--;
        graph[from].push_back({to, cost});
        graph[to].push_back({from, cost});
    }

    vector<ll> dis = dijkstra(0, graph);
    int farV = -1;
    ll farDis = -LINF;
    for (int i = 0; i < n; i++) {
        if (farDis < dis[i]) farV = i, farDis = dis[i];
    }
    dis = dijkstra(farV, graph);
    farDis = -LINF;
    for (int i = 0; i < n; i++) {
        if (farDis < dis[i]) farV = i, farDis = dis[i];
    }

    cout << farDis << endl;
    return 0;
}
0