> #include<iostream.h>
> 
> struct junc
> {
> 	char Ci;//初始灯的颜色
> 	int riC;//初始颜色的持续时间
> 	int tiB;//蓝灯的持续时间
> 	int tiP;//紫灯的持续时间
> 	int index;
> 	int pre;
> 	int time;//走到这个路口的最短时间
> };
> 
> struct edge
> {
> 	int from;
> 	int to;
> };
> 
> class Graph
> {
> public: 
> 	int**r;
> 	int *Mark;
> 	int numOfJuc,numOfRoad;//交通路口数目和路的数目
> 	Graph(int n,int m);
> 	edge FirstEdge(int v); //以V为起点的第一条边
> 	edge NextEdge(edge e); //以e的起点为起点的下一条边
> 	bool IsEdge(edge e);   //判断是否是边
> };
> 
> class minHeap
> {
> public:
> 	int size;
> 	int currentSize;
> 	junc*heap;
> 	minHeap(int n);
> 	void SiftDown(int left); 
> 	void SiftUp(int p);
> 	void BuildHeap();  //建最小值堆
> 	bool removeMin(junc&d);    //删掉堆中最小值
> 	void Insert(junc &t);     //插入值
> 	bool empty();
> };
> 
> Graph::Graph(int n,int m)
> {
> 	int i,j;
> 	numOfRoad=m;
> 	numOfJuc=n;
> 	r=new int*[numOfJuc+1];//记录每条路的长度
> 	Mark=new int[numOfJuc+1];
> 
> 	for(i=0;i<=numOfJuc;i++)
> 		r[i]=new int[numOfJuc+1];
> 
> 	for(i=0;i<=numOfJuc;i++)
> 		for(j=0;j<=numOfJuc;j++)
> 			r[i][j]=1000000;
> }
> 
> edge Graph::FirstEdge(int v)
> {
> 	edge e;
> 	int i;
> 	e.from=v;
> 	e.to=-1;
> 	for(i=1;i<=numOfJuc;i++){
> 		if(r[v][i]<=100){
> 			e.to=i;
>     		break;
> 		}
> 	}
> 	return e;
> }
> 
> bool Graph::IsEdge(edge e)
> {
> 	if(e.to!=-1)
>     	return true;
> 	else
> 		return false;
> }
> 
> edge Graph::NextEdge(edge e)
> {
> 	edge nexte;
> 	nexte.from=e.from;
> 	nexte.to=-1;
> 	int i;
> 	for(i=e.to+1;i<=numOfJuc;i++){
> 		if(r[e.from][i]<=100)
> 		{
> 			nexte.to=i;
>     		break;
> 		}
> 	}
> 	return nexte;
> }
> 
> minHeap::minHeap(int n)
> {
> 	size=n;
> 	currentSize=0;
> 	heap=new junc[size];
> }
> 
> void minHeap::BuildHeap()
> {
> 	int i;
> 	for(i=currentSize/2-1;i>=0;i--)
> 		SiftDown(i);
> }
> 
> void minHeap::SiftDown(int left)
> {
> 	int i=left;
> 	int j=2*left+1;
> 	junc tmp=heap[i];
> 
> 	while(j<currentSize){
>         if(j<currentSize-1 && heap[j].time>heap[j+1].time)
> 	    	j++;
> 		if(tmp.time>heap[j].time){
> 			heap[i].time=heap[j].time;
> 			i=j;
> 			j=2*j+1;
> 		}
> 		else
> 			break;
> 	}
> 	heap[j]=tmp;
> }
> 
> bool minHeap::removeMin(junc&d)
> {
>     junc tmp;
> 	if(currentSize==0)
> 		return false;
> 
>    	currentSize--;
> 
> 	tmp=heap[0];
> 	heap[0]=heap[currentSize];
> 	heap[currentSize]=tmp;
> 
> 	if(currentSize>1)
> 		SiftDown(0);
> 	d=heap[currentSize];
> 	return true;
> }
> 
> void minHeap::SiftUp(int p)
> {
> 	int tmppos=p;
> 	junc tmp=heap[tmppos];
> 	while(tmppos>0 && heap[(tmppos-1)/2].time>tmp.time)
> 	{
> 		heap[(tmppos-1)/2]=heap[tmppos];
> 		tmppos=(tmppos-1)/2;
> 	}
> 	heap[tmppos]=tmp;
> }
> 
> void minHeap::Insert(junc& t)
> {
> 	heap[currentSize]=t;
> 	SiftUp(currentSize);
> 	currentSize++;
> }
> 
> bool minHeap::empty()
> {
> 	if(currentSize==0)
> 		return true;
> 	else
> 		return false;
> }
> /////////////////////////////////////////////////////////////////////////////////////////
> 
> int Wait(int from,int to, junc*D)
> {
> 	int t1=0,t2=0;
> 	char c1=D[from].Ci;
> 	char c2=D[to].Ci;
> 
> 	if(D[from].time<D[from].riC)//时间小于初始状态维持的时间
> 		t1=D[from].riC-D[from].time;//记录变颜色还需多长时间
> 	else
> 	{
> 		t1=(D[from].time-D[from].riC)%(D[from].tiB+D[from].tiP);
> 		if(c1=='B')//初始为蓝色
> 		{
> 			if(t1<D[from].tiP)
> 			{
> 		    	t1=D[from].tiP-t1;
> 				c1='P';
> 			}
> 			else
> 			{
> 				t1=D[from].tiB+D[from].tiP-t1;
> 				c1='B';
> 			}
> 		}
> 		else
> 		{
> 			if(t1<D[from].tiB)
> 			{
> 				t1=D[from].tiB-t1;
> 				c1='B';
> 			}
> 			else
> 			{
> 				t1=D[from].tiP+D[from].tiB-t1;
> 				c1='P';
> 			}
> 		}
> 	}//cout<<"t1="<<t1<<endl;
> 
> 	if(D[from].time<D[to].riC)
> 		t2=D[to].riC-D[from].time;
> 	else
> 	{
> 		t2=(D[from].time-D[to].riC)%(D[to].tiB+D[to].tiP);
> 		if(c2=='P')
> 		{
> 			if(t2<D[to].tiB)
> 			{
> 	    		t2=D[to].tiB-t2;
> 				c2='B';
> 			}
> 			else
> 			{
> 				t2=D[to].tiP+D[to].tiB-t2;
> 				c2='P';
> 			}
> 		}
> 		else
> 		{	
> 			if(t2<D[to].tiP)
> 			{
> 				t2=D[to].tiP-t2;
> 				c2='P';
> 			}
> 			else
> 			{
> 				t2=D[to].tiB+D[to].tiP-t2;
> 				c2='B';
> 			}
> 		}
> 	}
> 	if(c1==c2)
> 		return 0;
> 	if(t1>t2)
> 		return t2;
> 	if(t1<t2)
>     	return t1;
> 
> 	if(c1=='B')
> 	{
> 		if(D[from].tiP!=D[to].tiB)
>     		D[from].tiP<D[to].tiB?t1+=D[from].tiP:t1+=D[to].tiB;
> 		else
> 		{
> 			if(D[from].tiB!=D[to].tiP)
> 				D[from].tiB<D[to].tiP?t1+=D[from].tiB:t1+=D[to].tiP;
> 			else
> 				return 1000000;
> 		}
> 	}
> 	else
> 	{	
> 		if(D[from].tiB!=D[to].tiP)
> 			D[from].tiB<D[to].tiP?t1+=D[from].tiB:t1+=D[to].tiP;
> 		else
> 		{
> 			if(D[from].tiP!=D[to].tiB)
> 				D[from].tiP<D[to].tiB?t1+=D[from].tiP:t1+D[to].tiB;
> 			else
> 				return 1000000;
> 		}
> 		return t1;
> 	}
> }
> 
> int Quickest(int s,int end,junc*D,Graph&G)
> {
> 	int i;
> 
> 	for(i=1;i<=G.numOfJuc;i++)
> 	{
> 		G.Mark[i]=0;
> 		D[i].index=i;
> 		D[i].pre=s;
> 		D[i].time=1000000;
> 	}
> 	D[s].time=0;
> 	minHeap H(G.numOfRoad);
> 	H.Insert(D[s]);
> 
> 	for(i=1;i<=G.numOfJuc;i++)
> 	{
> 		junc d;
> 		while(!H.empty())
> 		{
> 			if(!H.removeMin(d))
> 				return 1000000;
> 			else
> 			{
> 		    	if(G.Mark[d.index]==0)
> 			    	break;
> 			}
> 		}
> 		if(d.index==end)
> 			return D[end].time;
> 		
> 		int v=d.index;
> 		G.Mark[v]=1;
> 		for(edge e=G.FirstEdge(v);G.IsEdge(e);e=G.NextEdge(e))
> 		{ 
> 			if(G.Mark[e.to] == 1)
> 				continue;
> 			int waitingTime=Wait(e.from,e.to,D);//计算需要等待的时间
> 			if(D[e.to].time>D[v].time+G.r[e.from][e.to]+waitingTime)
> 			{
> 				D[e.to].time=D[v].time+G.r[e.from][e.to]+waitingTime;
> 				D[e.to].pre=v;
> 				H.Insert(D[e.to]);
> 			}
> 		}
> 	}
> 
> 	return D[end].time;
> }
> 
> 
> void main()
> {
> 	int s,d;//起点和终点
> 	int juc,road;
> 	int i;
> 
> 	cin>>s>>d;
> 	cin>>juc>>road;
> 
> 	Graph G(juc,road);
> 
> //	minHeap H(road);
> 
> 	junc*D;
> 	D=new junc[G.numOfJuc+1];
> 
> 	for(i=1;i<=G.numOfJuc;i++)
> 		cin>>D[i].Ci>>D[i].riC>>D[i].tiB>>D[i].tiP;
> 
> 	for(i=1;i<=G.numOfRoad;i++)
> 	{
> 		int tmps,tmpd,weight;
> 		cin>>tmps>>tmpd>>weight;
> 		G.r[tmps][tmpd]=G.r[tmpd][tmps]=weight;
> 	}
> 
> 	int t=Quickest(s,d,D,G);
> 
> 	if(t<1000000)
>     	cout<<t<<endl;
> 	else
> 		cout<<0<<endl;
> }
> 		
>