[POJ] 3169 - Layout - http://kuoe0.ch/1519/poj-3169-layout/

3169 - Layout.cpp

#include <iostream>
#include <queue>
using namespace std;
#define MAXN 1010

struct EDGE {
	int v, w, next;
};

EDGE edge[ 3000010 ];
int adj[ MAXN ], dis[ MAXN ], cnt[ MAXN ];
bool inque[ MAXN ];
int n, e1, e2, total;
queue< int > que;

void addEdge( int a, int b, int w ) {
	edge[ total ].v = b, edge[ total ].w = w, edge[ total ].next = adj[ a ];
	adj[ a ] = total;
	++total;
}

int SPFA( int sr ) {
	int now, next, i;
	memset( dis, 63, sizeof( dis ) );
	memset( cnt, 0, sizeof( cnt ) );
	while ( !que.empty() )
		que.pop(); 
	dis[ sr ] = 0;
	inque[ sr ] = 1, cnt[ sr ] = n;
	que.push( sr );
	
	while ( !que.empty() ) {
		now = que.front();
		que.pop();
		inque[ now ] = 0;
		for ( i = adj[ now ]; i != -1; i = edge[ i ].next ) {
			EDGE temp = edge[ i ];
			next = edge[ i ].v;
			if ( dis[ now ] + edge[ i ].w < dis[ next ] ) {
				dis[ next ] = dis[ now ] + edge[ i ].w;
				if ( !inque[ next ] ) {
					++cnt[ next ];
					if ( cnt[ next ] > n )
						return -1;
					
					que.push( next );
					inque[ next ] = 1;
				}
			}
		}
	}
	return dis[ n ] != dis[ 0 ] ? dis[ n ] : -2;
}

int main() {
	int i, a, b, w;
	
	while ( ~scanf( "%d %d %d", &n, &e1, &e2 ) ) {
		total = 0;
		memset( adj, -1, sizeof( adj ) );
		for ( i = 0; i < e1; ++i ) {
			scanf( "%d %d %d", &a, &b, &w );
			addEdge( a, b, w );
		}
		for ( i = 0; i < e2; ++i ) {
			scanf( "%d %d %d", &a, &b, &w );
			addEdge( b, a, -w );
		}
		printf( "%d\n", SPFA( 1 ) );
	}
	return 0;
}