shortest-path/restore-shortest-path.hpp

• View this file on GitHub
• Last update: 2026-06-08 17:59:24+09:00
• Include: #include "shortest-path/restore-shortest-path.hpp"

Depends on

• グラフテンプレート (graph/graph-template.hpp)
• グラフユーティリティ (graph/graph-utility.hpp)

Verified with

• verify/verify-yosupo-graph/yosupo-shortest-path.test.cpp

Code

#pragma once

#include "../graph/graph-utility.hpp"

// restore shortest path from S to G
template <typename T>
vector<int> restore_shortest_path(WeightedGraph<T> &g, vector<T> &d, int S,
                                  int G) {
  int N = g.size();
  WeightedGraph<T> rev(g.size());
  for (int i = 0; i < N; i++)
    for (auto &e : g[i]) rev[e.to].emplace_back(e.to, i, e.cost);
  vector<int> ret;
  ret.push_back(G);
  int p = G;
  T dist = d[G];
  vector<int> vis(N, 0);
  vis[G] = 1;
  do {
    int nxt = -1;
    T nval = numeric_limits<T>::max() / 2;
    for (auto &e : rev[p]) {
      if (vis[e.to] || d[e.to] + e.cost != dist) continue;
      if (d[e.to] != -1 && d[e.to] < nval) nval = d[e.to], nxt = e.to;
    }
    ret.push_back((vis[nxt] = 1, dist = nval, p = nxt));
  } while (p != S);
  reverse(begin(ret), end(ret));
  return ret;
}

#line 2 "shortest-path/restore-shortest-path.hpp"

#line 2 "graph/graph-utility.hpp"

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

template <typename T>
struct edge {
  int src, to;
  T cost;

  edge(int _to, T _cost) : src(-1), to(_to), cost(_cost) {}
  edge(int _src, int _to, T _cost) : src(_src), to(_to), cost(_cost) {}

  edge &operator=(const int &x) {
    to = x;
    return *this;
  }

  operator int() const { return to; }
};
template <typename T>
using Edges = vector<edge<T>>;
template <typename T>
using WeightedGraph = vector<Edges<T>>;
using UnweightedGraph = vector<vector<int>>;

// Input of (Unweighted) Graph
UnweightedGraph graph(int N, int M = -1, bool is_directed = false,
                      bool is_1origin = true) {
  UnweightedGraph g(N);
  if (M == -1) M = N - 1;
  for (int _ = 0; _ < M; _++) {
    int x, y;
    cin >> x >> y;
    if (is_1origin) x--, y--;
    g[x].push_back(y);
    if (!is_directed) g[y].push_back(x);
  }
  return g;
}

// Input of Weighted Graph
template <typename T>
WeightedGraph<T> wgraph(int N, int M = -1, bool is_directed = false,
                        bool is_1origin = true) {
  WeightedGraph<T> g(N);
  if (M == -1) M = N - 1;
  for (int _ = 0; _ < M; _++) {
    int x, y;
    cin >> x >> y;
    T c;
    cin >> c;
    if (is_1origin) x--, y--;
    g[x].emplace_back(x, y, c);
    if (!is_directed) g[y].emplace_back(y, x, c);
  }
  return g;
}

// Input of Edges
template <typename T>
Edges<T> esgraph([[maybe_unused]] int N, int M, int is_weighted = true,
                 bool is_1origin = true) {
  Edges<T> es;
  for (int _ = 0; _ < M; _++) {
    int x, y;
    cin >> x >> y;
    T c;
    if (is_weighted)
      cin >> c;
    else
      c = 1;
    if (is_1origin) x--, y--;
    es.emplace_back(x, y, c);
  }
  return es;
}

// Input of Adjacency Matrix
template <typename T>
vector<vector<T>> adjgraph(int N, int M, T INF, int is_weighted = true,
                           bool is_directed = false, bool is_1origin = true) {
  vector<vector<T>> d(N, vector<T>(N, INF));
  for (int _ = 0; _ < M; _++) {
    int x, y;
    cin >> x >> y;
    T c;
    if (is_weighted)
      cin >> c;
    else
      c = 1;
    if (is_1origin) x--, y--;
    d[x][y] = c;
    if (!is_directed) d[y][x] = c;
  }
  return d;
}

/**
 * @brief グラフテンプレート
 */
#line 4 "graph/graph-utility.hpp"

// 一般のグラフのstからの距離！！！！
// unvisited nodes : d = -1
vector<int> Depth(const UnweightedGraph &g, int start = 0) {
  int n = g.size();
  vector<int> ds(n, -1);
  ds[start] = 0;
  queue<int> q;
  q.push(start);
  while (!q.empty()) {
    int c = q.front();
    q.pop();
    int dc = ds[c];
    for (auto &d : g[c]) {
      if (ds[d] == -1) {
        ds[d] = dc + 1;
        q.push(d);
      }
    }
  }
  return ds;
}

// Depth of Rooted Weighted Tree
// unvisited nodes : d = -1
template <typename T>
vector<T> Depth(const WeightedGraph<T> &g, int start = 0) {
  vector<T> d(g.size(), -1);
  auto dfs = [&](auto rec, int cur, T val, int par = -1) -> void {
    d[cur] = val;
    for (auto &dst : g[cur]) {
      if (dst == par) continue;
      rec(rec, dst, val + dst.cost, cur);
    }
  };
  dfs(dfs, start, 0);
  return d;
}

// Diameter of Tree
// return value : { {u, v}, length }
pair<pair<int, int>, int> Diameter(const UnweightedGraph &g) {
  auto d = Depth(g, 0);
  int u = max_element(begin(d), end(d)) - begin(d);
  d = Depth(g, u);
  int v = max_element(begin(d), end(d)) - begin(d);
  return make_pair(make_pair(u, v), d[v]);
}

// Diameter of Weighted Tree
// return value : { {u, v}, length }
template <typename T>
pair<pair<int, int>, T> Diameter(const WeightedGraph<T> &g) {
  auto d = Depth(g, 0);
  int u = max_element(begin(d), end(d)) - begin(d);
  d = Depth(g, u);
  int v = max_element(begin(d), end(d)) - begin(d);
  return make_pair(make_pair(u, v), d[v]);
}

// nodes on the path u-v ( O(N) )
template <typename G>
vector<int> Path(G &g, int u, int v) {
  vector<int> ret;
  int end = 0;
  auto dfs = [&](auto rec, int cur, int par = -1) -> void {
    ret.push_back(cur);
    if (cur == v) {
      end = 1;
      return;
    }
    for (int dst : g[cur]) {
      if (dst == par) continue;
      rec(rec, dst, cur);
      if (end) return;
    }
    if (end) return;
    ret.pop_back();
  };
  dfs(dfs, u);
  return ret;
}

/**
 * @brief グラフユーティリティ
 */
#line 4 "shortest-path/restore-shortest-path.hpp"

// restore shortest path from S to G
template <typename T>
vector<int> restore_shortest_path(WeightedGraph<T> &g, vector<T> &d, int S,
                                  int G) {
  int N = g.size();
  WeightedGraph<T> rev(g.size());
  for (int i = 0; i < N; i++)
    for (auto &e : g[i]) rev[e.to].emplace_back(e.to, i, e.cost);
  vector<int> ret;
  ret.push_back(G);
  int p = G;
  T dist = d[G];
  vector<int> vis(N, 0);
  vis[G] = 1;
  do {
    int nxt = -1;
    T nval = numeric_limits<T>::max() / 2;
    for (auto &e : rev[p]) {
      if (vis[e.to] || d[e.to] + e.cost != dist) continue;
      if (d[e.to] != -1 && d[e.to] < nval) nval = d[e.to], nxt = e.to;
    }
    ret.push_back((vis[nxt] = 1, dist = nval, p = nxt));
  } while (p != S);
  reverse(begin(ret), end(ret));
  return ret;
}

Back to top page