結果

問題 No.3113 The farthest point
コンテスト
ユーザー よいちなすの
提出日時 2025-04-18 21:39:15
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
RE  
実行時間 -
コード長 1,565 bytes
コンパイル時間 1,456 ms
コンパイル使用メモリ 170,924 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2025-04-18 21:39:22
合計ジャッジ時間 6,700 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 1 RE * 2
other RE * 33
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9;

struct Edge {
    int to, weight;
};

vector<Edge> graph[100000];
vector<int> dist(100000, INF);

// ダイクストラ法を使って最短経路を求める
void dijkstra(int start, int N) {
    fill(dist.begin(), dist.begin() + N, INF);
    dist[start] = 0;
    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;
        int d = pq.top().first;
        pq.pop();

        if (d > dist[u]) continue;

        for (const auto& edge : graph[u]) {
            int v = edge.to, w = edge.weight;
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
}

int main() {
    int N, M;
    cin >> N >> M;

    // グラフの入力
    for (int i = 0; i < M; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        u--; v--;  // 0-indexedに変換
        graph[u].push_back({v, w});
        graph[v].push_back({u, w});
    }

    // 最初に任意の頂点からダイクストラ
    dijkstra(0, N);
    int farthest = 0;
    for (int i = 1; i < N; i++) {
        if (dist[i] > dist[farthest]) {
            farthest = i;
        }
    }

    // 次に最も遠い頂点から再度ダイクストラ
    dijkstra(farthest, N);
    int diameter = 0;
    for (int i = 0; i < N; i++) {
        diameter = max(diameter, dist[i]);
    }

    cout << diameter << endl;

    return 0;
}
0