最短路
(C++/graph/ShortestPath.hpp)

• View this file on GitHub
• Last update: 2025-06-14 01:07:36+09:00
• Include: #include "C++/graph/ShortestPath.hpp"

Required by

• 重み付きグラフライブラリ (C++/graph/WeightedGraph.hpp)
• 木の直径 (C++/graph/diameter.hpp)

Verified with

• test/dijkstra.test.cpp
• test/shortestpath.test.cpp
• test/spfa.test.cpp
• test/tree_diameter.test.cpp
• test/warshallfloyd.test.cpp

Code

#pragma once

#pragma GCC diagnostic ignored "-Wreorder"

#include <vector>
#include <algorithm>
namespace man {
struct ShortestPath {
private:
    const std::vector<long long> cost;
    const std::vector<int> src;
public:
    ShortestPath(const std::vector<long long> &cost, const std::vector<int> &src): cost(cost), src(src){}
    inline bool is_thru(const int i) const noexcept { return src[i] != -1; }
    inline std::vector<int> path(int i) noexcept {
        std::vector<int> ret;
        for(; i != -1; i = src[i]) {
            ret.emplace_back(i);
        }
        std::ranges::reverse(ret);
        return ret;
    }
    inline std::vector<long long> get() const noexcept { return cost; }
};
}

/**
 * @brief 最短路
 */

#line 2 "C++/graph/ShortestPath.hpp"

#pragma GCC diagnostic ignored "-Wreorder"

#include <vector>
#include <algorithm>
namespace man {
struct ShortestPath {
private:
    const std::vector<long long> cost;
    const std::vector<int> src;
public:
    ShortestPath(const std::vector<long long> &cost, const std::vector<int> &src): cost(cost), src(src){}
    inline bool is_thru(const int i) const noexcept { return src[i] != -1; }
    inline std::vector<int> path(int i) noexcept {
        std::vector<int> ret;
        for(; i != -1; i = src[i]) {
            ret.emplace_back(i);
        }
        std::ranges::reverse(ret);
        return ret;
    }
    inline std::vector<long long> get() const noexcept { return cost; }
};
}

/**
 * @brief 最短路
 */

Back to top page