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

• Re:谁能帮我看看哪里有错？晚上要交了十分着急 (6503) ds00548090 2006-11-29 18:20:56