graph/shortest_path/path_recover.cpp

• View this file on GitHub
• Last update: 2026-01-31 00:52:12+08:00

Verified with

• test/shortest_path_dense.test.cpp
• test/shortest_path_sparse.test.cpp

Code

vi recover(vi &pre, int t) {
  if (pre[t] == -1) return {};
  vi path = {t};
  while(pre[path.back()] != path.back())
    path.emplace_back(pre[path.back()]);
  ranges::reverse(path);
  return path;
}

#line 1 "graph/shortest_path/path_recover.cpp"
vi recover(vi &pre, int t) {
  if (pre[t] == -1) return {};
  vi path = {t};
  while(pre[path.back()] != path.back())
    path.emplace_back(pre[path.back()]);
  ranges::reverse(path);
  return path;
}

Back to top page