Poj Solution 1158

http://poj.org/problem?id=1158

#include <stdio.h>
#include <memory.h>
#include <vector>
#include <queue>
using namespace std;

int n, begin, end;
int b[300], p[300], sum[300];
int r[300];

typedef pair<int,int> p_i;

bool s[300][30000];

vector< p_i > e[300];
struct cmp {
    bool operator()( const p_i &a, const p_i &b ) const {
        return a.second > b.second;
    }
};

priority_queue< p_i, vector<p_i>, cmp > q;

void input( ) {
    int i, v, m, y, x;
    char c[2];
    scanf( "%d%d", &begin, &end );
    begin--, end--;

    scanf( "%d%d", &n, &m );
    for( i=0; i<n; i++ ) {
        scanf( "%1s%d%d%d", c, r+i, b+i, p+i );
        if( c[0] == 'P' )
            r[i] = b[i]+p[i]-r[i];
        else
            r[i] = b[i]-r[i];
        sum[i] = b[i]+p[i];
    }

    for( i=0; i<m; i++ ) {
        scanf( "%d%d%d", &x, &y, &v );
        e[x-1].push_back( p_i( y-1, v ) );
        e[y-1].push_back( p_i( x-1, v ) );
    }
}

int main( ) {
    int i, x, t, y, tt;

    input();

    q.push( p_i( begin, 0 ) );

    while( !q.empty() ) {
        x = q.top().first;
        t = q.top().second;
        
        if( x == end )
            break;
        
        if( t > n*200 ) {
            t = 0;
            break;
        }

        q.pop();

        if( !s[x][t+1] ) {
            q.push( p_i( x, t+1 ) );
            s[x][t+1] = true;
        }


        for( i=0; i<e[x].size(); i++ ) {
            y = e[x][i].first;
            if( !s[y][tt=t+e[x][i].second] && ((t+r[x])%sum[x]>=b[x]) == ((t+r[y])%sum[y]>=b[y]) ) {
                s[y][tt] = true;
                q.push( p_i( y, tt ) );
            }
        }
    }

    if( q.empty() )
        printf( "0n" );
    else
        printf( "%dn", t );

    return 0;
}