:warning: 最短経路木 O((E+V)logE)
(graph_tree/shortest_path_tree_dijkstra.hpp)

Depends on

Code

#pragma once
#include<vector>
#include"graph_template.hpp"

#pragma once
#include<vector>
#include<queue>
#include<functional>
#include<tuple>
#include<limits>
#include"graph_template.hpp"

/**
 * @brief 最短経路木 O((E+V)logE)
 */

template<typename T,typename F=std::less<T>>
std::vector<int> shortest_path_tree_dijkstra(const graph_w<T>& list,int s,T zero=0,T inf=std::numeric_limits<T>::max(),F f=F()){
    std::priority_queue<std::pair<T,int>,std::vector<pair<T,int>>,std::greater<std::pair<T,int>>>que;
    std::vector<T>diff(list.size(),inf);
    diff[s]=zero;
    que.push(make_pair(T(),s));
    std::vector<int> par(list.size(),-1);
    while(!que.empty()){
        auto d=que.top();
        que.pop();
        T x;
        int now;
        tie(x,now)=d;
        for(auto d2:list[now]){
            T sa;
            int to;
            tie(to,sa)=d2;
            if(f(diff[now]+sa,diff[to])){
                diff[to]=diff[now]+sa;
                par[to]=now;
                que.emplace(diff[to],to);
            }
        }
    }
    return par;
}
Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.9.1/x64/lib/python3.9/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
  File "/opt/hostedtoolcache/Python/3.9.1/x64/lib/python3.9/site-packages/onlinejudge_verify/languages/cplusplus.py", line 193, in bundle
    bundler.update(path)
  File "/opt/hostedtoolcache/Python/3.9.1/x64/lib/python3.9/site-packages/onlinejudge_verify/languages/cplusplus_bundle.py", line 312, in update
    raise BundleErrorAt(path, i + 1, "#pragma once found in a non-first line")
onlinejudge_verify.languages.cplusplus_bundle.BundleErrorAt: graph_tree/shortest_path_tree_dijkstra.hpp: line 5: #pragma once found in a non-first line
Back to top page