3169.txt

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

Source

Problem Id:3169  User Id:fzk 
Memory:180K  Time:46MS
Language:G++  Result:Accepted

Source 

#include <stdio.h>
#include <memory.h>

int dis[10001];

struct edge {
	int from, to, dis;
}e[21000];
int m, n;

//x1-x2<=e
void insert( int x1, int x2, int d ) {
	e[m].from = x2;
	e[m].to = x1;
	e[m].dis = d;
	m++;
}

bool release( ) {
	bool key = false;
	for( int i=0; i<m; i++ )
		if( dis[ e[i].from ] + e[i].dis < dis[ e[i].to ] ) {
			dis[ e[i].to ] = dis[ e[i].from ] + e[i].dis;
			key = true;
		}
	return key;
}

void clac( ) {
	int i;
	for( i=2; i<=n; i++ )
		dis[i] = (1<<30);
	dis[1] = 0;
	
	bool key = false;

	for( i=0; i<n; i++ )
		if( !(key = release( )) )
			break;
	if( key )
		printf( "-1\n" );
	else if( dis[n] == (1<<30) )
		printf( "-2\n" );
	else
		printf( "%d\n", dis[n] );
}

int main( ) {
	int i, a, b, d, s1, s2;
	m = 0;
	scanf( "%d%d%d", &n, &s1, &s2 );
	
	while( s1-- ) {
		scanf( "%d%d%d", &a, &b, &d );
		insert( b, a, d );
	}

	while( s2-- ) {
		scanf( "%d%d%d", &a, &b, &d );
		insert( a, b, -d );
	}

	for( i=1; i<n; i++ )
		insert( i, i+1, 0 );

	clac( );

	return 0;
}