#include <iostream.h>

struct junct_info
{
	int Ci;
	int ric;
	int tiB;
	int tiP;
	int pre;
	int time;
};

struct junct
{
	int time;
	int id;
};

junct_info jt[300];
int map[300][300];
int visit[300];

junct* heap;
int heapsize;

//返回在t时刻，从j1驶向j2所需最少等待时间
int wait( int time, junct_info j1, junct_info j2)
{
	int c1, r1, c2, r2;
	int t1, t2;
	if ( time < j1.ric )
	{
		c1 = j1.Ci;
		r1 = j1.ric - time;
	}
	else
	{
		t1 = ( time - j1.ric ) % ( j1.tiB + j1.tiP );
		if ( j1.Ci == 0 )
		{
			if ( t1 < j1.tiP )
			{
				c1 = 1;
				r1 = j1.tiP - t1;
			}
			else
			{
				c1 = 0;
				r1 = j1.tiP + j1.tiB - t1;
			}
		}
		else
		{
			if ( t1 < j1.tiB )
			{
				c1 = 0;
				r1 = j1.tiB - t1;
			}
			else
			{
				c1 = 1;
				r1 = j1.tiP + j1.tiB - t1;
			}
		}
	}

	if ( time < j2.ric )
	{
		c2 = j2.Ci;
		r2 = j2.ric - time;
	}
	else
	{
		t2 = ( time - j2.ric ) % ( j2.tiB + j2.tiP );
		if ( j2.Ci == 0 )
		{
			if ( t2 < j2.tiP )
			{
				c2 = 1;
				r2 = j2.tiP - t2;
			}
			else
			{
				c2 = 0;
				r2 = j2.tiP + j2.tiB - t2;
			}
		}
		else
		{
			if ( t2 < j2.tiB )
			{
				c2 = 0;
				r2 = j2.tiB - t2;
			}
			else
			{
				c2 = 2;
				r2 = j2.tiP + j2.tiB - t2;
			}
		}
	}

	if ( c1 == c2 )
		return 0;
	else if ( r1 != r2 )
		return ( r1 < r2 ) ? r1 : r2;
	else if ( c1 == 0 )
	{
		if ( j1.tiP != j2.tiB )
			return  r1 + (( j1.tiP < j2.tiB ) ? j1.tiP : j2.tiB);
		else if ( j1.tiB != j2.tiP )
			return r1 + j1.tiP + ( j1.tiB < j2.tiP ) ? j1.tiB : j2.tiP;
		else
			return -1;
	}
	else
	{
		if ( j1.tiB != j2.tiP )
			return  r1 + ( j1.tiB < j2.tiP ) ? j1.tiB : j2.tiP;
		else if ( j1.tiP != j2.tiB )
			return r1 + j1.tiB + ( j1.tiP < j2.tiB ) ? j1.tiP : j2.tiB;
		else
			return -1;
	}
}

//add a element into heap
void heap_insert( junct j)
{
	int i, c;
	i = heapsize;
	heapsize++;
	while( i > 0 )
	{
		c = ( i - 1 ) / 2;
		if ( heap[c].time < j.time )
			break;
		heap[i].id = heap[c].id;
		heap[i].time = heap[c].time;
		i = c;
	}
	heap[i].id = j.id;
	heap[i].time = j.time;
}

//delete the min-element from the heap
junct heap_delmin()
{
	int i, c;
	junct ret;
	ret.id = heap[0].id;
	ret.time = heap[0].time;
	heapsize--;
	i = 0;
	while( i < heapsize / 2 )
	{
		c = i * 2 + 1;
		if ( c + 1 < heapsize && heap[c].time > heap[c+1].time )
			c++;
		if ( heap[heapsize].time < heap[c].time )
			break;
		heap[i].id = heap[c].id;
		heap[i].time = heap[c].time;
		i = c;
	}
	heap[i].id = heap[heapsize].id;
	heap[i].time = heap[heapsize].time;
	return ret;
}

void main()
{
	int src, des;
	int n, m;
	int i, id1, id2, k, d, index;
	char c;
	junct j, j1;
	bool found;
	int path[300], pathlen;

	cin >> src >> des;
	src--;
	des--;
	cin >> n >> m;
	for ( i = 0; i < n; i++)
	{
		cin >> c >> jt[i].ric >> jt[i].tiB >> jt[i].tiP;
		if ( c == 'B' )
			jt[i].Ci = 0;
		else
			jt[i].Ci = 1;
		jt[i].pre = -1;
		jt[i].time = -1;
		visit[i] = 0;
	}
	for ( i = 0; i < n; i++)
		for ( k = 0; k < n; k++)
			map[i][k] = 0;
	for ( i = 0; i < m; i++)
	{
		cin >> id1 >> id2;
		cin >> map[id1-1][id2-1];
		map[id2-1][id1-1] = map[id1-1][id2-1];
	}

	heap = new junct[m];
	heapsize = 0;
	
	j.id = src;
	j.time = jt[src].time = 0;
	heap_insert(j);
	
	for ( i = 0; i < n; i++)
	{
		found = 0;
		while( heapsize > 0 )
		{
			j = heap_delmin();
			if ( visit[j.id] == 0 )
			{
				found = 1;
				break;
			}
		}
		if ( !found )
			break;

		if ( j.id == des )
			break;
		
		visit[j.id] = 1;
		
		for ( k = 0; k < n; k++)
		{
			if ( visit[k] == 0 && map[k][j.id] != 0 )
			{
				d = wait( j.time, jt[j.id], jt[k]);
				if ( d == -1 )
					continue;
				if ( j.time + d < jt[k].time || jt[k].time == -1)
				{  //~~~~~~~~~~~~~~~~~~~~~~~
					j1.id = k;
					j1.time = j.time + d + map[k][j.id];
					jt[k].time = j1.time;
					jt[k].pre = j.id;
					heap_insert(j1);
				}
			}
		}
	}
	
	if ( j.id == des )
	{
		cout << j.time << endl;
	}
	else
		cout << 0 << endl;
	delete[]heap;
}

• 这个，没什么特别的吧 (4677) frkstyc 2005-11-29 23:30:17