2679.txt

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

Problem Id:2679  User Id:fzk 
Memory:13128K  Time:78MS
Language:C++  Result:Accepted

Source 

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

using namespace std;
const int size = 1110;

struct edge
{
	int len;
	int fee;
	edge *next;
};

edge e[size][size];
edge *link[size];
bool sign[size];
int m, n, begin, end;
int fee[size];

void search( int b )
{
	int a;
	sign[b] = true;
	for( a=0; a<n; a++ )
		if( !sign[a] && e[a][b].fee == fee[a] )
			search( a );
}


bool init( )
{
	int i, j, u, v, f1, f2, l;
	if( scanf( "%d %d %d %d", &n, &m, &begin, &end ) != 4 )
		return false;

	for( i=0; i<n; i++ )
	{
		fee[i] = 800;
		for( j=0; j<n; j++ )
			e[i][j].fee = 999;
	}

	char c[10];
	
	for( i=0; i<m; i++ )
	{
		scanf( "%1s", c );
		scanf( "%d,%d,%d[%d]%d)", &u, &v, &f1, &l, &f2 );

		if( e[u][v].fee > f1 || ( e[u][v].fee == f1 && e[u][v].len > l ) )
		{
			e[u][v].fee = f1, e[u][v].len = l;
			if( fee[u] > f1 ) fee[u] = f1;
		}

		if( e[v][u].fee > f2 || ( e[v][u].fee == f2 && e[v][u].len > l ) )
		{
			e[v][u].fee = f2, e[v][u].len = l;
			if( fee[v] > f2 ) fee[v] = f2;
		}
	}

	memset( link, 0, sizeof link );

	for( i=0; i<n; i++ )
	{
		for( j=0; j<n; j++ )
			if( e[i][j].fee == fee[i] )
			{
				e[i][j].next = link[i];
				link[i] = &e[i][j];
			}
	}

	memset( sign, 0, sizeof sign );
	search( end );

	return true;
}

int dis[size];
int len[size];
bool flag[size];

int dijstra( )
{
	int i, j, k, t;
	edge *p;

	memset( flag, 0, sizeof flag );
	for( i=0; i<n; i++ )
		len[i] = 999999;

	len[begin] = 0;
	for( i=0; i<n; i++ )
	{
		k = end;
		for( j=0; j<n; j++ )
			if( sign[j] && !flag[j] && len[j] < len[k] )
				k = j;
		
		if( k == end )
			return len[k];

		flag[k] = true;
		
		for( p=link[k]; p; p=p->next )
		{
			j = p-e[k];
			if( dis[j] - dis[k] == p->fee && len[j] > ( t = len[k] + p->len ) )
				len[j] = t;
		}
	}

	return 0;
}


void doit( )
{
	int i, j, t, l;
	edge *p;

	if( !sign[begin] )
	{
		printf( "VOID\n" );
		return;
	}

	for( i=0; i<n; i++ )
		dis[i] = 999999;

	dis[begin] = 0;

	for( i=0; i<n-1; i++ )
	{
		for( j=0; j<n; j++ )
		if( sign[j] )
		{
			for( p = link[j]; p; p=p->next )
			if( ( t = dis[j] + p->fee ) < dis[ l=p-e[j] ] )
				dis[l] = t;
		}
	}

	for( j=0; j<n; j++ )
	if( sign[j] )
	{
		for( p = link[j]; p; p=p->next )
		if( sign[ l=p-e[j] ] && dis[j]+p->fee < dis[l] )
			break;

		if( p ) break;
	}

	if( p )
	{
		printf( "UNBOUND\n" );
		return;
	}

	printf( "%d %d\n", dis[end], dijstra() );
}
	

int main( )
{
	while( init( ) )
		doit( );

	return 0;
}