セグメント木ではなく sparse table の構造を用いて区間に辺を張ることもできる.この場合空間計算量は $O(n\log n + m)$,時間計算量は構築 $O(n\log n)$,辺の追加 $O(1)$,Dijkstra 法 $O((n\log n + m) \log (n\log n + m)))$ となる.特に辺が多いときに高速であるという利点があるが,空間計算量が大きくなるので注意が必要である.Sqrt tree の構造を用いることもできるが狂気である.
#pragma once
#include <bit>
#include <vector>
#include "shortest_path.hpp"
template < typename T >
class RangeEdgeGraph {
public:
RangeEdgeGraph () = default ;
explicit RangeEdgeGraph ( int n )
: size ( std :: bit_ceil (( unsigned int ) n )), G ( 4 * size ) {
for ( int i = 1 ; i < size ; ++ i ) {
int l = 2 * i , r = 2 * i + 1 ;
G [ i ]. emplace_back ( l , 0 );
G [ i ]. emplace_back ( r , 0 );
G [ l + 2 * size ]. emplace_back ( i + 2 * size , 0 );
G [ r + 2 * size ]. emplace_back ( i + 2 * size , 0 );
}
for ( int i = size ; i < 2 * size ; ++ i )
G [ i ]. emplace_back ( i + 2 * size , 0 );
}
void add_edge ( int l1 , int r1 , int l2 , int r2 , T w ) {
int idx = G . size ();
for ( l1 += size , r1 += size ; l1 < r1 ; l1 >>= 1 , r1 >>= 1 ) {
if ( l1 & 1 ) G [ l1 + 2 * size ]. emplace_back ( idx , 0 ), ++ l1 ;
if ( r1 & 1 ) -- r1 , G [ r1 + 2 * size ]. emplace_back ( idx , 0 );
}
std :: vector < std :: pair < int , T >> node ;
for ( l2 += size , r2 += size ; l2 < r2 ; l2 >>= 1 , r2 >>= 1 ) {
if ( l2 & 1 ) node . emplace_back ( l2 ++ , w );
if ( r2 & 1 ) node . emplace_back ( -- r2 , w );
}
G . push_back ( node );
}
std :: vector < T > dist ( int s ) const {
auto dist = dijkstra ( G , s + size );
return std :: vector < T > ( dist . begin () + size , dist . begin () + 2 * size );
}
private:
int size ;
std :: vector < std :: vector < std :: pair < int , T >>> G ;
};
/*
Implementation with a sparse table
template <typename T>
class RangeEdgeGraph {
public:
RangeEdgeGraph() = default;
explicit RangeEdgeGraph(int n)
: n(n), b(std::bit_width((unsigned int)n)), G(2 * n * b) {
for (int i = 1; i < b; ++i) {
for (int j = 0; j + (1 << i) <= n; ++j) {
int k = n * i + j;
int l = n * (i - 1) + j;
int r = l + (1 << (i - 1));
G[k].emplace_back(l, 0);
G[k].emplace_back(r, 0);
G[n * b + l].emplace_back(n * b + k, 0);
G[n * b + r].emplace_back(n * b + k, 0);
}
}
for (int j = 0; j < n; ++j) G[j].emplace_back(n * b + j, 0);
}
void add_edge(int l1, int r1, int l2, int r2, T w) {
int idx = G.size();
std::vector<std::pair<int, T>> node;
int i = std::bit_width((unsigned int)(r1 - l1)) - 1;
G[n * b + n * i + l1].emplace_back(idx, 0);
G[n * b + n * i + r1 - (1 << i)].emplace_back(idx, 0);
i = std::bit_width((unsigned int)(r2 - l2)) - 1;
node.emplace_back(n * i + l2, w);
node.emplace_back(n * i + r2 - (1 << i), w);
G.push_back(node);
}
std::vector<T> dist(int s) const {
auto dist = dijkstra(G, s);
return std::vector<T>(dist.begin(), dist.begin() + n);
}
private:
int n, b;
std::vector<std::vector<std::pair<int, T>>> G;
};
*/
#line 2 "graph/range_edge_graph.hpp"
#include <bit>
#include <vector>
#line 2 "graph/shortest_path.hpp"
#include <limits>
#include <queue>
#include <tuple>
#include <utility>
#line 7 "graph/shortest_path.hpp"
/*
* Bellman-Ford Algorithm
*/
template < typename T >
std :: vector < T > bellman_ford ( const std :: vector < std :: tuple < int , int , T >>& G ,
int V , int s ) {
constexpr T INF = std :: numeric_limits < T >:: max ();
std :: vector < T > dist ( V , INF );
dist [ s ] = 0 ;
for ( int i = 0 ; i < V ; ++ i ) {
for ( auto & [ s , t , w ] : G ) {
if ( dist [ s ] != INF && dist [ t ] > dist [ s ] + w ) {
dist [ t ] = dist [ s ] + w ;
if ( i == V - 1 ) return {};
}
}
}
return dist ;
}
/*
* Floyd-Warshall Algorithm
*/
template < typename T >
void floyd_warshall ( std :: vector < std :: vector < T >>& dist ) {
const int V = dist . size ();
for ( int k = 0 ; k < V ; ++ k ) {
for ( int i = 0 ; i < V ; ++ i ) {
for ( int j = 0 ; j < V ; ++ j ) {
dist [ i ][ j ] = std :: min ( dist [ i ][ j ], dist [ i ][ k ] + dist [ k ][ j ]);
}
}
}
}
/*
* Dijkstra's Algorithm
*/
template < typename T >
std :: vector < T > dijkstra ( const std :: vector < std :: vector < std :: pair < int , T >>>& G ,
int s ) {
std :: vector < T > dist ( G . size (), std :: numeric_limits < T >:: max ());
dist [ s ] = 0 ;
using P = std :: pair < T , int > ;
std :: priority_queue < P , std :: vector < P > , std :: greater < P >> pq ;
pq . emplace ( 0 , s );
while ( ! pq . empty ()) {
auto [ d , v ] = pq . top ();
pq . pop ();
if ( dist [ v ] < d ) continue ;
for ( auto & [ u , w ] : G [ v ]) {
if ( dist [ u ] > d + w ) {
dist [ u ] = d + w ;
pq . emplace ( dist [ u ], u );
}
}
}
return dist ;
}
template < typename T >
std :: pair < std :: vector < T > , std :: vector < int >> shortest_path_tree (
const std :: vector < std :: vector < std :: pair < int , T >>>& G , int s ) {
std :: vector < T > dist ( G . size (), std :: numeric_limits < T >:: max ());
std :: vector < int > par ( G . size (), - 1 );
dist [ s ] = 0 ;
using P = std :: pair < T , int > ;
std :: priority_queue < P , std :: vector < P > , std :: greater < P >> pq ;
pq . emplace ( 0 , s );
while ( ! pq . empty ()) {
auto [ d , v ] = pq . top ();
pq . pop ();
if ( dist [ v ] < d ) continue ;
for ( auto & [ u , w ] : G [ v ]) {
if ( dist [ u ] > d + w ) {
dist [ u ] = d + w ;
par [ u ] = v ;
pq . emplace ( dist [ u ], u );
}
}
}
return { dist , par };
}
/*
* Breadth-First Search
*/
std :: vector < int > bfs ( const std :: vector < std :: vector < int >>& G , int s ) {
std :: vector < int > dist ( G . size (), - 1 );
dist [ s ] = 0 ;
std :: queue < int > que ;
que . push ( s );
while ( ! que . empty ()) {
int v = que . front ();
que . pop ();
for ( int u : G [ v ]) {
if ( dist [ u ] == - 1 ) {
dist [ u ] = dist [ v ] + 1 ;
que . push ( u );
}
}
}
return dist ;
}
/*
* Dial's Algorithm
*/
std :: vector < int > dial ( const std :: vector < std :: vector < std :: pair < int , int >>>& G ,
int s , int w ) {
std :: vector < int > dist ( G . size (), std :: numeric_limits < int >:: max ());
dist [ s ] = 0 ;
std :: vector < std :: vector < int >> buckets ( w * G . size (), std :: vector < int > ());
buckets [ 0 ]. push_back ( s );
for ( int d = 0 ; d < ( int ) buckets . size (); ++ d ) {
while ( ! buckets [ d ]. empty ()) {
int v = buckets [ d ]. back ();
buckets [ d ]. pop_back ();
if ( dist [ v ] < d ) continue ;
for ( auto & [ u , w ] : G [ v ]) {
if ( dist [ u ] > d + w ) {
dist [ u ] = d + w ;
buckets [ dist [ u ]]. push_back ( u );
}
}
}
}
return dist ;
}
#line 6 "graph/range_edge_graph.hpp"
template < typename T >
class RangeEdgeGraph {
public:
RangeEdgeGraph () = default ;
explicit RangeEdgeGraph ( int n )
: size ( std :: bit_ceil (( unsigned int ) n )), G ( 4 * size ) {
for ( int i = 1 ; i < size ; ++ i ) {
int l = 2 * i , r = 2 * i + 1 ;
G [ i ]. emplace_back ( l , 0 );
G [ i ]. emplace_back ( r , 0 );
G [ l + 2 * size ]. emplace_back ( i + 2 * size , 0 );
G [ r + 2 * size ]. emplace_back ( i + 2 * size , 0 );
}
for ( int i = size ; i < 2 * size ; ++ i )
G [ i ]. emplace_back ( i + 2 * size , 0 );
}
void add_edge ( int l1 , int r1 , int l2 , int r2 , T w ) {
int idx = G . size ();
for ( l1 += size , r1 += size ; l1 < r1 ; l1 >>= 1 , r1 >>= 1 ) {
if ( l1 & 1 ) G [ l1 + 2 * size ]. emplace_back ( idx , 0 ), ++ l1 ;
if ( r1 & 1 ) -- r1 , G [ r1 + 2 * size ]. emplace_back ( idx , 0 );
}
std :: vector < std :: pair < int , T >> node ;
for ( l2 += size , r2 += size ; l2 < r2 ; l2 >>= 1 , r2 >>= 1 ) {
if ( l2 & 1 ) node . emplace_back ( l2 ++ , w );
if ( r2 & 1 ) node . emplace_back ( -- r2 , w );
}
G . push_back ( node );
}
std :: vector < T > dist ( int s ) const {
auto dist = dijkstra ( G , s + size );
return std :: vector < T > ( dist . begin () + size , dist . begin () + 2 * size );
}
private:
int size ;
std :: vector < std :: vector < std :: pair < int , T >>> G ;
};
/*
Implementation with a sparse table
template <typename T>
class RangeEdgeGraph {
public:
RangeEdgeGraph() = default;
explicit RangeEdgeGraph(int n)
: n(n), b(std::bit_width((unsigned int)n)), G(2 * n * b) {
for (int i = 1; i < b; ++i) {
for (int j = 0; j + (1 << i) <= n; ++j) {
int k = n * i + j;
int l = n * (i - 1) + j;
int r = l + (1 << (i - 1));
G[k].emplace_back(l, 0);
G[k].emplace_back(r, 0);
G[n * b + l].emplace_back(n * b + k, 0);
G[n * b + r].emplace_back(n * b + k, 0);
}
}
for (int j = 0; j < n; ++j) G[j].emplace_back(n * b + j, 0);
}
void add_edge(int l1, int r1, int l2, int r2, T w) {
int idx = G.size();
std::vector<std::pair<int, T>> node;
int i = std::bit_width((unsigned int)(r1 - l1)) - 1;
G[n * b + n * i + l1].emplace_back(idx, 0);
G[n * b + n * i + r1 - (1 << i)].emplace_back(idx, 0);
i = std::bit_width((unsigned int)(r2 - l2)) - 1;
node.emplace_back(n * i + l2, w);
node.emplace_back(n * i + r2 - (1 << i), w);
G.push_back(node);
}
std::vector<T> dist(int s) const {
auto dist = dijkstra(G, s);
return std::vector<T>(dist.begin(), dist.begin() + n);
}
private:
int n, b;
std::vector<std::vector<std::pair<int, T>>> G;
};
*/