1158.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

 

#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( "0\n" );
	else
		printf( "%d\n", t );

	return 0;
}