test/aoj/grl_5_a.test.cpp

View this file on GitHub
Last update: 2022-12-24 16:49:35+09:00
Problem: https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/5/GRL_5_A

Depends on

Code

#define PROBLEM                                                                \
  "https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/5/GRL_5_A"

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

#include "../../src/graph/diameter.hpp"
#include "../../src/graph/template.hpp"

int main() {
  int n;
  cin >> n;
  Diameter<int> diameter(n);
  for (int i = 0; i < n - 1; i++) {
    int s, t, w;
    cin >> s >> t >> w;
    diameter.add_edge(s, t, w);
  }
  cout << diameter.calc() << endl;
  return 0;
}

#line 1 "test/aoj/grl_5_a.test.cpp"
#define PROBLEM                                                                \
  "https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/5/GRL_5_A"

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

#line 2 "src/graph/diameter.hpp"

#line 4 "src/graph/diameter.hpp"
using namespace std;

#line 2 "src/graph/template.hpp"

#line 4 "src/graph/template.hpp"
using namespace std;

template <typename T = long long> struct Edge {
  int from, to;
  T cost;
  Edge(int from, int to, T cost = 1) : from(from), to(to), cost(cost) {}
};

template <typename T = long long> using Edges = vector<Edge<T>>;
template <typename T = long long> using Graph = vector<Edges<T>>;

template <typename T = long long> using Matrix = vector<vector<T>>;
#line 7 "src/graph/diameter.hpp"

template <typename T = long long> struct Diameter {
private:
  using P = pair<T, int>;
  int v;
  Graph<T> g;

public:
  Diameter(int v) : v(v), g(v) {}

  void add_edge(int from, int to, T cost = 1) {
    g[from].emplace_back(from, to, cost);
    g[to].emplace_back(to, from, cost);
  }

  T calc() {
    P f = dfs(0, -1);
    P s = dfs(f.second, -1);
    return s.first;
  }

private:
  P dfs(int i, int parent) {
    P ret = make_pair((T)0, i);
    for (auto edge : g[i]) {
      if (edge.to == parent) {
        continue;
      }
      auto next = dfs(edge.to, i);
      next.first += edge.cost;
      ret = max(ret, next);
    }
    return ret;
  }
};
#line 9 "test/aoj/grl_5_a.test.cpp"

int main() {
  int n;
  cin >> n;
  Diameter<int> diameter(n);
  for (int i = 0; i < n - 1; i++) {
    int s, t, w;
    cin >> s >> t >> w;
    diameter.add_edge(s, t, w);
  }
  cout << diameter.calc() << endl;
  return 0;
}