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;
}

```
This entry was posted in poj. Bookmark the permalink.