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

• View this file on GitHub
• Last update: 2024-02-29 11:41:45+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>
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){}
    bool is_thru(const int i){ return src[i] != -1; }
    std::vector<int> path(int i) {
        std::vector<int> res;
        for(; i != -1; i = src[i]) {
            res.emplace_back(i);
        }
        std::ranges::reverse(res);
        return res;
    }
    std::vector<long long> get() const { return cost; }
};

/**
 * @brief 最短路
 */

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

#pragma GCC diagnostic ignored "-Wreorder"

#include <vector>
#include <algorithm>
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){}
    bool is_thru(const int i){ return src[i] != -1; }
    std::vector<int> path(int i) {
        std::vector<int> res;
        for(; i != -1; i = src[i]) {
            res.emplace_back(i);
        }
        std::ranges::reverse(res);
        return res;
    }
    std::vector<long long> get() const { return cost; }
};

/**
 * @brief 最短路
 */

Back to top page