#include "graph_tree/dijkstra_fast.hpp"
#pragma once #include<vector> #include<tuple> #include<functional> #include<ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/priority_queue.hpp> #include"graph_template.hpp" /** * @brief ダイクストラ O(E+VlogE) */ template<typename T,typename F=std::less<T>,typename Add=std::plus<T>> struct dijkstra{ int s; std::vector<T> diff; std::vector<int> par; dijkstra(const graph_w<T>& list,int s,T zero=T(),T inf=std::numeric_limits<T>::max(),F f=F(),Add add=Add()):s(s){ int n=list.size(); diff.resize(n,inf); par.resize(n,-1); diff[s]=zero; auto cmp=[f](auto s,auto t){return f(t.first,s.first);}; using pq_t=__gnu_pbds::priority_queue<std::pair<T,int>,decltype(cmp),__gnu_pbds::pairing_heap_tag>; pq_t que(cmp); typename pq_t::point_iterator node[n]; for(int i=0;i<n;i++)node[i]=que.push(std::make_pair(inf,i)); que.modify(node[s],std::make_pair(zero,s)); while(!que.empty()){ T p; int now; std::tie(p,now)=que.top(); if(p==inf)break; que.pop(); for(auto d:list[now]){ auto next=add(p,d.second); if(f(next,diff[d.first])){ diff[d.first]=next; par[d.first]=now; que.modify(node[d.first],std::make_pair(next,d.first)); } } } } T operator[](int idx){ return diff[idx]; } bool reachable(int t){ return par[t]!=-1; } std::vector<int> get_path(int t){ std::vector<int>res; while(t!=s){ res.push_back(t); t=par[t]; } res.push_back(s); std::reverse(res.begin(),res.end()); return res; } };
#line 2 "graph_tree/dijkstra_fast.hpp" #include<vector> #include<tuple> #include<functional> #include<ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/priority_queue.hpp> #line 4 "graph_tree/graph_template.hpp" #include<iostream> /** * @brief グラフテンプレート */ using graph=std::vector<std::vector<int>>; template<typename T> using graph_w=std::vector<std::vector<std::pair<int,T>>>; graph load_graph(int n,int m){graph g(n);for(int i=0;i<m;++i){int s,t;std::cin>>s>>t;--s;--t;g[s].push_back(t);g[t].push_back(s);}return g;} graph load_digraph(int n,int m){graph g(n);for(int i=0;i<m;++i){int s,t;std::cin>>s>>t;--s;--t;g[s].push_back(t);}return g;} graph load_graph0(int n,int m){graph g(n);for(int i=0;i<m;++i){int s,t;std::cin>>s>>t;g[s].push_back(t);g[t].push_back(s);}return g;} graph load_digraph0(int n,int m){graph g(n);for(int i=0;i<m;++i){int s,t;std::cin>>s>>t;g[s].push_back(t);}return g;} graph load_tree(int n){graph g(n);for(int i=0;i<n-1;++i){int s,t;std::cin>>s>>t;--s;--t;g[s].push_back(t);g[t].push_back(s);}return g;} graph load_tree0(int n){graph g(n);for(int i=0;i<n-1;++i){int s,t;std::cin>>s>>t;g[s].push_back(t);g[t].push_back(s);}return g;} graph load_treep(int n){graph g(n);for(int i=0;i<n-1;++i){int t;std::cin>>t;g[i+1].push_back(t);g[t].push_back(i+1);}return g;} template<typename T>graph_w<T> load_graph_weight(int n,int m){graph_w<T> g(n);for(int i=0;i<m;++i){int s,t;T u;std::cin>>s>>t>>u;--s;--t;g[s].emplace_back(t,u);g[t].emplace_back(s,u);}return g;} template<typename T>graph_w<T> load_digraph_weight(int n,int m){graph_w<T> g(n);for(int i=0;i<m;++i){int s,t;T u;std::cin>>s>>t>>u;--s;--t;g[s].emplace_back(t,u);}return g;} template<typename T>graph_w<T> load_graph0_weight(int n,int m){graph_w<T> g(n);for(int i=0;i<m;++i){int s,t;T u;std::cin>>s>>t>>u;g[s].emplace_back(t,u);g[t].emplace_back(s,u);}return g;} template<typename T>graph_w<T> load_digraph0_weight(int n,int m){graph_w<T> g(n);for(int i=0;i<m;++i){int s,t;T u;std::cin>>s>>t>>u;g[s].emplace_back(t,u);}return g;} template<typename T>graph_w<T> load_tree_weight(int n){graph_w<T> g(n);for(int i=0;i<n-1;++i){int s,t;T u;std::cin>>s>>t>>u;--s;--t;g[s].emplace_back(t,u);g[t].emplace_back(s,u);}return g;} template<typename T>graph_w<T> load_tree0_weight(int n){graph_w<T> g(n);for(int i=0;i<n-1;++i){int s,t;T u;std::cin>>s>>t>>u;g[s].emplace_back(t,u);g[t].emplace_back(s,u);}return g;} template<typename T>graph_w<T> load_treep_weight(int n){graph_w<T> g(n);for(int i=0;i<n-1;++i){int t;T u;std::cin>>t>>u;g[i+1].emplace_back(t,u);g[t].emplace_back(i+1,u);}return g;} #line 8 "graph_tree/dijkstra_fast.hpp" /** * @brief ダイクストラ O(E+VlogE) */ template<typename T,typename F=std::less<T>,typename Add=std::plus<T>> struct dijkstra{ int s; std::vector<T> diff; std::vector<int> par; dijkstra(const graph_w<T>& list,int s,T zero=T(),T inf=std::numeric_limits<T>::max(),F f=F(),Add add=Add()):s(s){ int n=list.size(); diff.resize(n,inf); par.resize(n,-1); diff[s]=zero; auto cmp=[f](auto s,auto t){return f(t.first,s.first);}; using pq_t=__gnu_pbds::priority_queue<std::pair<T,int>,decltype(cmp),__gnu_pbds::pairing_heap_tag>; pq_t que(cmp); typename pq_t::point_iterator node[n]; for(int i=0;i<n;i++)node[i]=que.push(std::make_pair(inf,i)); que.modify(node[s],std::make_pair(zero,s)); while(!que.empty()){ T p; int now; std::tie(p,now)=que.top(); if(p==inf)break; que.pop(); for(auto d:list[now]){ auto next=add(p,d.second); if(f(next,diff[d.first])){ diff[d.first]=next; par[d.first]=now; que.modify(node[d.first],std::make_pair(next,d.first)); } } } } T operator[](int idx){ return diff[idx]; } bool reachable(int t){ return par[t]!=-1; } std::vector<int> get_path(int t){ std::vector<int>res; while(t!=s){ res.push_back(t); t=par[t]; } res.push_back(s); std::reverse(res.begin(),res.end()); return res; } };