getFarthestVertex(最遠頂点を求める)

1
auto res = getFarthestVertex(g,s);

1
struct getFarthestVertex_return {
2
  int v, cost;
3
};
4
getFarthestVertex_return getFarthestVertex(DirectedGraph &_g, int _v) {
5
  queue<pair<int, int>> q;
6
  vector<int> t(_g.n, -1);
7
  q.push({_v, 0});
8
  getFarthestVertex_return res = {-1, -1};
9
  while (!q.empty()) {
10
    auto p = q.front();
11
    q.pop();
12
    bool tr = true;
13
    for (auto &i : _g.g[p.first])
14
      if (t[i.to] == -1) {
15
        tr = false;
16
        q.push({i.to, p.second + i.cost});
17
        t[i.to] = p.second + i.cost;
18
      }
19
    if (tr)
20
      res = {p.first, p.second};
21
  }
22
  return res;
23
}