> #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;
> }
> 
> 
> 
> 
> 
>