HR Liars ( System of difference constraints )

https://www.hackerrank.com/challenges/liars
差分约束系统 - 维基百科，自由的百科全书
Well, it is a well known trick.
For any inequality, take a[ u ] + W ≥ a[ v ], it will be equivalent to having a unidirectional edge with weight W, from u to v. Having many equations will work as well. And to solve minimum a[ i ] for each i, where some base a[ 0 ] is determined, it is simply to find maximum distance from 0 to i. Why is this? Because if there is a path from u to v with weight 3, and another with weight 5, we will have to choose the one with 5 to satisfy the inequality ( d[ u ] + 3 ≥ d[ v ] and d[ u ] + 5 ≥ d[ v ], in this case obviously d[ v ] should be 5 instead of 3 ). And to solve the maximum a[ i ], simply run minimum distance instead.
For this problem, having
a[ i ] = number of liars in range [ 1, i ],
we will only have to put all inequalities that should be satisfied and run SSSP. ( Single Source Shortest Path )
In order to have a[ l - 1 ] + W == a[ r ], we will only have to define to inequalities
a[ l - 1 ] + W ≥ a[ r ] and a[ r ] - W ≥ a[ l - 1 ]
Note that a[ i + 1 ] ≥ a[ i ], a[ i + 1 ] - 1 ≥ a[ i ], a[ i ] + 1 ≤ a[ i + 1 ].

void spfaMax( const vector< vector< pii > > &G, vi &dis ){
    fill( dis.begin(), dis.end(), -INF );
    queue< int > que;
    vi inq( G.size() );
    que.push( 0 );
    dis[ 0 ] = 0;
    while( !que.empty() ){
        int u = que.front();
        que.pop();
        inq[ u ] = 0;
        for( pii e : G[ u ] ){
            int d = e.first;
            int v = e.second;
            if( dis[ v ] < dis[ u ] + d ){
                dis[ v ] = dis[ u ] + d;
                if( !inq[ v ] )
                    inq[ v ] = 1,
                    que.push( v );
            }
        }
    }
}

void spfaMin( const vector< vector< pii > > &G, vi &dis ){
    fill( dis.begin(), dis.end(), INF );
    queue< int > que;
    vi inq( G.size() );
    que.push( 0 );
    dis[ 0 ] = 0;
    while( !que.empty() ){
        int u = que.front();
        que.pop();
        inq[ u ] = 0;
        for( pii e : G[ u ] ){
            int d = e.first;
            int v = e.second;
            if( dis[ v ] > dis[ u ] + d ){
                dis[ v ] = dis[ u ] + d;
                if( !inq[ v ] )
                    inq[ v ] = 1,
                    que.push( v );
            }
        }
    }
}

void solve(){
    int N, M; cin >> N >> M;

    vector< vector< pii > > Gmin( N + 1 ), Gmax( N + 1 );
    for( int i = 0; i < M; ++i ){
        int a, b, c; cin >> a >> b >> c;
        Gmin[ a - 1 ].push_back( { c, b } );
        Gmin[ b ].push_back( { -c, a - 1 } );
        Gmax[ a - 1 ].push_back( { c, b } );
        Gmax[ b ].push_back( { -c, a - 1 } );
    }
    
    for( int i = 0; i < N; ++i )
        Gmin[ i ].push_back( { 0, i + 1 } ),
        Gmin[ i + 1 ].push_back( { -1, i } );

    vi dis_min( N + 1 );
    spfaMax( Gmin, dis_min );
    cout << dis_min[ N ] << " ";

    for( int i = 0; i < N; ++i )
        Gmax[ i ].push_back( { 1, i + 1 } ),
        Gmax[ i + 1 ].push_back( { 0, i } );

    vi dis_max( N + 1 );
    spfaMin( Gmax, dis_max );
    cout << dis_max[ N ] << "\n";
}