2360.txt

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

#include <stdio.h>
#include <string>
#include <vector>
#include <queue>
#include <memory.h>
#include <algorithm>

using namespace std;

typedef pair< string, int > city;

const int INF = 99999999;

vector< city > c;
int id[1000];
int dis[610][610], n;

inline int minusit( int a, int b )
{
	return ( a-b+1440 ) % 1440;
}

bool cmp( int a, int b )
{
	return c[a]<c[b];
}

void init()
{
	int m, a, b, t, h, i, tt, j, k;
	char w[100];
	city ct;

	scanf( "%d", &m );

	c.clear();

	for( i=0; i<=600; i++ )
	for( j=0; j<=600; j++ )
		dis[i][j] = INF;

	while( m-- )
	{
		scanf( "%d", &h );
		
		t = 0;
		for( i=0; i<h; i++ )
		{
			scanf( "%d:%d %s", &a, &b, w );
			t += a*60 + b;
			ct.first = w;
			ct.second = t%1440;
		
			k = find( c.begin(), c.end(), ct ) - c.begin();
			
			if( k == c.size() )
				c.push_back( ct );

			if( i )	dis[j][k] = t - tt;

			j = k, tt = t;
		}
	}

	n = c.size();
	for( i=0; i<n; i++ )
		id[i] = i;

	sort( id, id+n, cmp );

	for( i=0; i<n; i++ )
	{
		for( j=i+1; j<n&&c[ id[j] ].first == c[ id[i] ].first; j++ )
			;

		if( i != j-1 )
		{
			for( k=i; k<j; k++ )
			{
				t = i+(k-i+1)%(j-i);
				dis[ id[k] ][ id[t] ] = minusit( c[ id[t] ].second , c[ id[k] ].second );
			}
		}
	}
}

vector< pair<int,int> > ans;

int main()
{
	int cas, i, j, k, t;
	char w1[100], w2[100];

	scanf( "%d", &cas );

	while( cas -- )
	{
		init();

		scanf( "%s %s", w1, w2 );

		for( i=0; i<n; i++ )
			if( c[i].first == w2 )
				dis[i][n] = 0;

		for( k=0; k<=n; k++ )
		for( i=0; i<=n; i++ )
		for( j=0; j<=n; j++ )
			if( ( t = dis[i][k] + dis[k][j] ) < dis[i][j] )
				dis[i][j] = t;


		ans.clear();

		for( i=0; i<n; i++ )
			if( c[i].first == w1 && dis[i][n] < INF )
				ans.push_back( pair<int,int>( c[i].second%1440, dis[i][n] ) );

		sort( ans.begin(), ans.end() );


		for( i=ans.size(); i>=0; i-- )
		for( j=0; j<ans.size(); j++ )
		{
			k = (j+1)%ans.size();
			if( j!=k && minusit( ans[k].first, ans[j].first  ) <= ans[j].second - ans[k].second )
				ans.erase( &ans[j] );
		}


		for( i=0; i<ans.size(); i++ )
			printf( "%0.2d:%0.2d %d:%0.2d\n", ans[i].first/60, ans[i].first%60, ans[i].second/60, ans[i].second%60 );
		printf( "\n" );
	}

	return 0;
}