// 誤解法(O(V^2)のダイクストラを用いたポテンシャル付きダイクストラ)チェック #ifndef INCLUDE_MODE #define INCLUDE_MODE // #define REACTIVE // #define USE_GETLINE #endif #ifdef INCLUDE_MAIN inline void Solve() { CEXPR( int , bound , 1e3 ); CIN_ASSERT( N , 2 , bound ); CIN_ASSERT( M , 1 , bound ); CIN_ASSERT( Q , 1 , bound ); using path_type = tuple; vector> e( N ); FOR( j , 0 , M ){ CIN_ASSERT( uj , 1 , N ); CIN_ASSERT( vj , 1 , N ); assert( uj != vj ); uj--; vj--; CIN_ASSERT( wj , -bound , bound ); e[uj].push_back( { vj , -wj , j } ); } auto edge = [&]( const int& i ){ return e[i]; }; Graph graph{ N , edge }; vector fixed( M , true ); auto on = [&]( const path_type& e ){ return fixed[get<2>( e )]; }; PotentialisedDijkstra pdijk{ graph , 0 , on , true }; assert( pdijk.Valid() ); // CEXPR( bool , many_edges , false ); CEXPR( bool , many_edges , true ); FOR( q , 0 , Q ){ CIN_ASSERT( j , 1 , M ); j--; fixed[j] = !fixed[j]; ll answer = get<1>( pdijk.GetDistance( many_edges ) )[N-1]; if( answer == pdijk.Infty() ){ COUT( "NaN" ); } else { COUT( -answer ); } } } REPEAT_MAIN(1); #else // INCLUDE_MAIN #ifdef INCLUDE_LIBRARY // https://github.com/p-adic/cpp // VVV ライブラリは以下に挿入する。 class is_ordered { private: is_ordered() = delete; template static constexpr auto Check( const T& t ) -> decltype( t < t , true_type() ); static constexpr false_type Check( ... ); public: template static constexpr const bool value = is_same_v< decltype( Check( declval() ) ) , true_type >; }; template typename T> struct hash> : public hash { inline size_t operator()( const T& n ) const; }; template using Map = conditional_t>,unordered_map,conditional_t,map,void>>; // Mapは // - unordered_map()がwell-formedならばunordered_map // - そうでなくoperator<(declval(),declval())がwell-formedならばmap // - そうでないならばvoid template typename T> inline size_t hash>::operator()( const T& n ) const { return hash::operator()( n.Represent() ); } #define DECLARATION_OF_CPOINT( POINT ) inline const U& POINT() const noexcept #define DECLARATION_OF_POINT( POINT ) inline U& POINT() noexcept #define DEFINITION_OF_CPOINT( POINT ) template inline const U& VirtualPointedSet::POINT() const noexcept { return Point(); } #define DEFINITION_OF_POINT( POINT ) template inline U& VirtualPointedSet::POINT() noexcept { return Point(); } // - インタフェースをなるべく抽象型で与えて仮想継承する。 // - 具体的構造が2種類以上あるものはもちろん抽象型を仮想継承する。 // - VirtualPointedSetのように具体的構造が1種類しかないものも仮想継承のコンストラクタ呼び出しを // 省略するためになるべく抽象型を用意する。 // - AbstractDijkstraのように全ての具体的構造が1つの具体的構造の派生である場合は // インタフェースを必要としない。 // - コンストラクタはなるべく省略できるようにするが、ポインタはメンバ変数にしない。 // - VirtualGraphのように具体的構造が2種類以上あるもので全てに共通の定義本体を持つ関数(Edge)が // 必要な場合は実装が膨れ上がらないように抽象型に関数の定義をし、そのため抽象型にメンバ変数が // 必要になる場合はコンストラクタを非自明なものにする // - 代わりにポインタを抽象型のメンバとして // 派生クラスのコンストラクタの定義内でアドレスを渡すようにすると、ムーブなどで意図せず // ポインタの指すアドレスが意図通りでなくなることに注意する。 template class UnderlyingSet { public: using type = U; }; template class VirtualPointedSet : virtual public UnderlyingSet { public: virtual const U& Point() const noexcept = 0; virtual U& Point() noexcept = 0; DECLARATION_OF_CPOINT( Unit ); DECLARATION_OF_CPOINT( Zero ); DECLARATION_OF_CPOINT( One ); DECLARATION_OF_CPOINT( Infty ); DECLARATION_OF_POINT( init ); DECLARATION_OF_POINT( root ); }; template class PointedSet : virtual public VirtualPointedSet { private: U m_b_U; public: inline PointedSet( const U& b_u = U() ); inline const U& Point() const noexcept; inline U& Point() noexcept; }; template class VirtualNSet : virtual public UnderlyingSet { public: virtual U Transfer( const U& u ) = 0; inline U Inverse( const U& u ); }; template class AbstractNSet : virtual public VirtualNSet { private: F_U& m_f_U; public: inline AbstractNSet( F_U& f_U ); inline U Transfer( const U& u ); }; template class VirtualMagma : virtual public UnderlyingSet { public: virtual U Product( const U& u0 , const U& u1 ) = 0; inline U Sum( const U& u0 , const U& u1 ); }; template class AdditiveMagma : virtual public VirtualMagma { public: inline U Product( const U& u0 , const U& u1 ); }; template class MultiplicativeMagma : virtual public VirtualMagma { public: inline U Product( const U& u0 , const U& u1 ); }; template class AbstractMagma : virtual public VirtualMagma { private: M_U& m_m_U; public: inline AbstractMagma( M_U& m_U ); inline U Product( const U& u0 , const U& u1 ); }; template inline PointedSet::PointedSet( const U& b_U ) : m_b_U( b_U ) {} template inline const U& PointedSet::Point() const noexcept { return m_b_U; } template inline U& PointedSet::Point() noexcept { return m_b_U; } DEFINITION_OF_CPOINT( Unit ); DEFINITION_OF_CPOINT( Zero ); DEFINITION_OF_CPOINT( One ); DEFINITION_OF_CPOINT( Infty ); DEFINITION_OF_POINT( init ); DEFINITION_OF_POINT( root ); template inline AbstractNSet::AbstractNSet( F_U& f_U ) : m_f_U( f_U ) { static_assert( is_invocable_r_v ); } template inline U AbstractNSet::Transfer( const U& u ) { return m_f_U( u ); } template inline U VirtualNSet::Inverse( const U& u ) { return Transfer( u ); } template inline AbstractMagma::AbstractMagma( M_U& m_U ) : m_m_U( m_U ) { static_assert( is_invocable_r_v ); } template inline U AdditiveMagma::Product( const U& u0 , const U& u1 ) { return u0 + u1; } template inline U MultiplicativeMagma::Product( const U& u0 , const U& u1 ) { return u0 * u1; } template inline U AbstractMagma::Product( const U& u0 , const U& u1 ) { return m_m_U( u0 , u1 ); } template inline U VirtualMagma::Sum( const U& u0 , const U& u1 ) { return Product( u0 , u1 ); } template class VirtualMonoid : virtual public VirtualMagma , virtual public VirtualPointedSet {}; template class AdditiveMonoid : virtual public VirtualMonoid , public AdditiveMagma , public PointedSet {}; template class MultiplicativeMonoid : virtual public VirtualMonoid , public MultiplicativeMagma , public PointedSet { public: inline MultiplicativeMonoid( const U& e_U ); }; template class AbstractMonoid : virtual public VirtualMonoid , public AbstractMagma , public PointedSet { public: inline AbstractMonoid( M_U& m_U , const U& e_U ); }; template inline MultiplicativeMonoid::MultiplicativeMonoid( const U& e_U ) : PointedSet( e_U ) {} template inline AbstractMonoid::AbstractMonoid( M_U& m_U , const U& e_U ) : AbstractMagma( m_U ) , PointedSet( e_U ) {} template class VirtualGroup : virtual public VirtualMonoid , virtual public VirtualPointedSet , virtual public VirtualNSet {}; template class AdditiveGroup : virtual public VirtualGroup , public AdditiveMonoid { public: inline U Transfer( const U& u ); }; template class AbstractGroup : virtual public VirtualGroup , public AbstractMonoid , public AbstractNSet { public: inline AbstractGroup( M_U& m_U , const U& e_U , I_U& i_U ); inline U Transfer( const U& u ); }; template inline AbstractGroup::AbstractGroup( M_U& m_U , const U& e_U , I_U& i_U ) : AbstractMonoid( m_U , e_U ) , AbstractNSet( i_U ) {} template inline U AbstractGroup::Transfer( const U& u ) { return this->m_i_U( u ); } template inline U AdditiveGroup::Transfer( const U& u ) { return -u; } // Enumeration:N->R1-->TとEnumeration_inv:T->R2-->Nは互いに逆写像である仮想関数。 template class VirtualGraph : virtual public UnderlyingSet { public: virtual R1 Enumeration( const int& i ) = 0; virtual R2 Enumeration_inv( const T& t ) = 0; inline void Reset(); virtual const int& size() const noexcept = 0; virtual E& edge() noexcept = 0; virtual ret_t Edge( const T& t ) = 0; }; template class EdgeImplimentation : virtual public VirtualGraph { private: int m_size; // 配列への参照を返す関数オブジェクトを構築して返す関数の返り値などの右辺値を受け取ることを // 許容したいので左辺値参照にはしない。 E m_edge; public: inline EdgeImplimentation( const int& size , E edge ); inline const int& size() const noexcept; inline E& edge() noexcept; inline ret_t Edge( const T& t ); }; template class Graph : public EdgeImplimentation { public: inline Graph( const int& size , E edge ); inline const int& Enumeration( const int& i ); inline const int& Enumeration_inv( const int& t ); template inline Graph GetGraph( F edge ) const; }; template class EnumerationGraph : public EdgeImplimentation,ret_t,E> { private: Enum_T& m_enum_T; Enum_T_inv& m_enum_T_inv; public: inline EnumerationGraph( const int& size , Enum_T& enum_T , Enum_T_inv& enum_T_inv , E edge ); inline ret_t Enumeration( const int& i ); inline ret_t Enumeration_inv( const T& t ); template inline EnumerationGraph GetGraph( F edge ) const; }; template EnumerationGraph( const int& size , Enum_T enum_T , Enum_T_inv enum_T_inv , E edge ) -> EnumerationGraph()(0)),Enum_T,Enum_T_inv,E>; // 推論補助のためにE::operator()はデフォルト引数が必要。 template class MemorisationGraph : public EdgeImplimentation { private: int m_length; vector m_memory; Map m_memory_inv; public: inline MemorisationGraph( const int& size , E edge ); // push_backする可能性のあるvectorなので参照にしないように注意 inline T Enumeration( const int& i ); inline const int& Enumeration_inv( const T& t ); inline void Reset(); template inline MemorisationGraph GetGraph( F edge ) const; }; template MemorisationGraph( const int& size , E edge ) -> MemorisationGraph()().back()),E>; template MemorisationGraph( const int& size , E edge ) -> MemorisationGraph(declval()().back())),E>; template inline EdgeImplimentation::EdgeImplimentation( const int& size , E edge ) : m_size( size ) , m_edge( move( edge ) ) { static_assert( is_constructible_v && is_constructible_v && is_invocable_v ); } template inline Graph::Graph( const int& size , E edge ) : EdgeImplimentation( size , move( edge ) ) {} template inline EnumerationGraph::EnumerationGraph( const int& size , Enum_T& enum_T , Enum_T_inv& enum_T_inv , E edge ) : EdgeImplimentation,ret_t,E>( size , move( edge ) ) , m_enum_T( enum_T ) , m_enum_T_inv( enum_T_inv ) {} template inline MemorisationGraph::MemorisationGraph( const int& size , E edge ) : EdgeImplimentation( size , move( edge ) ) , m_length() , m_memory() , m_memory_inv() { static_assert( is_invocable_v && is_invocable_v ); } template inline const int& Graph::Enumeration( const int& i ) { return i; } template inline ret_t EnumerationGraph::Enumeration( const int& i ) { return m_enum_T( i ); } template inline T MemorisationGraph::Enumeration( const int& i ) { assert( 0 <= i && i < m_length ); return m_memory[i]; } template inline const int& Graph::Enumeration_inv( const int& i ) { return i; } template inline ret_t EnumerationGraph::Enumeration_inv( const T& t ) { return m_enum_T_inv( t ); } template inline const int& MemorisationGraph::Enumeration_inv( const T& t ) { if( m_memory_inv.count( t ) == 0 ){ assert( m_length < this->size() ); m_memory.push_back( t ); return m_memory_inv[t] = m_length++; } return m_memory_inv[t]; } template void VirtualGraph::Reset() {} template inline void MemorisationGraph::Reset() { m_length = 0; m_memory.clear(); m_memory_inv.clear(); } template inline const int& EdgeImplimentation::size() const noexcept { return m_size; } template inline E& EdgeImplimentation::edge() noexcept { return m_edge; } template inline ret_t EdgeImplimentation::Edge( const T& t ) { return m_edge( t ); } template template inline Graph Graph::GetGraph( F edge ) const { return Graph( this->size() , move( edge ) ); } template template inline EnumerationGraph EnumerationGraph::GetGraph( F edge ) const { return EnumerationGraph( this->size() , m_enum_T , m_enum_T_inv , move( edge ) ); } template template inline MemorisationGraph MemorisationGraph::GetGraph( F edge ) const { return MemorisationGraph( this->size() , move( edge ) ); } #define BELLMAN_FORD_BODY( INITIALISE_PREV , SET_PREV ) \ const U& zero = m_M.Zero(); \ const U& infty = this->Infty(); \ assert( zero < infty ); \ const int& size = m_G.size(); \ auto&& i_start = m_G.Enumeration_inv( t_start ); \ assert( 0 <= i_start && i_start < size ); \ vector found( size ); \ vector weight( size , infty ); \ found[i_start] = true; \ weight[i_start] = 0; \ INITIALISE_PREV; \ \ for( int length = 0 ; length < size ; length++ ){ \ \ for( int i = 0 ; i < size ; i++ ){ \ \ if( found[i] ){ \ \ const U& weight_i = weight[i]; \ assert( weight_i != infty ); \ auto&& edge_i = m_G.Edge( m_G.Enumeration( i ) ); \ \ for( auto itr = edge_i.begin() , end = edge_i.end() ; itr != end ; itr++ ){ \ \ auto&& j = m_G.Enumeration_inv( itr->first ); \ const U& edge_ij = itr->second; \ U temp = m_M.Sum( weight_i , edge_ij ); \ U& weight_j = weight[j]; \ \ if( weight_j > temp ){ \ \ found[j] = true; \ weight_j = move( temp ); \ SET_PREV; \ \ } \ \ } \ \ } \ \ } \ \ } \ \ bool valid = true; \ \ for( int i = 0 ; i < size && valid ; i++ ){ \ \ if( found[i] ){ \ \ const U& weight_i = weight[i]; \ auto&& edge_i = m_G.Edge( m_G.Enumeration( i ) ); \ \ for( auto itr = edge_i.begin() , end = edge_i.end() ; itr != end ; itr++ ){ \ \ auto&& j = m_G.Enumeration_inv( itr->first ); \ const U& edge_ij = itr->second; \ U& weight_j = weight[j]; \ const U temp = m_M.Sum( weight_i , edge_ij ); \ \ if( weight_j > temp ){ \ \ valid = false; \ break; \ \ } \ \ } \ \ } \ \ } \ // GRAPHはグラフG=(V_G,E_G:T->(T \times U)^{< \omega})に相当する型。 // 入力の範囲内で要件 // (0) Mは全順序可換モノイド構造である。 // (1) inftyがE_Gの値の各成分の第2成分|V_G|個以下の和で表せるいかなる数よりも大きい。 // が成り立つ場合にのみサポート。 // 単一始点全終点最短経路探索/経路復元なしO(|V_G| |E_G|) // 単一始点全終点最短経路探索/経路復元ありO(|V_G| |E_G|) template class AbstractBellmanFord : public PointedSet { private: GRAPH& m_G; // コンストラクタに引数が必要なMultiplicativeMonoidなどはstaticメンバ関数による // 参照返しがしにくく、コンストラクタの返り値である右辺値を受け取ることを許容したいので // 左辺値参照にはしない。 MONOID m_M; public: inline AbstractBellmanFord( GRAPH& G , MONOID M , const U& infty ); // 負の閉路が存在すればfalse、存在しなければtrueを第1成分に返す。 tuple> GetDistance( const inner_t& t_start , const bool& dummy = true ); template