#include <stdio.h>
#include <string.h>

#define VN 303
#define AN 28003
#define MAX 900000000

int remaind[VN],du[VN][2];
int dis[VN];

typedef struct
{
	int arcnum;
	int vexnum;      
	int gra[VN][VN]; //gra[i][j]记录从i到j的时间
}graph;
graph G;

int arc[AN][2];  //记录第i个灯B和P颜色的周期，B存于arc[i][0]，P存于varc[i][1]
int light[VN];  //记录起始时各灯的颜色，0：B  1：P
int begin,end;  //起始位置和终止位置

int tim(int from,int to,int ti)
{
	//返回从from到to点需要花费的时间，如果不可达则返回－1

	int a,b,p,ff,tt;
	int re1,re2,ll1,ll2;

	tt=ti;
	b=du[from][0];
	p=du[from][1];
	ll1=light[from];
	re1=remaind[from];

	///////////////////////////
	if(ti<re1)
	{
		re1=re1-ti;
	}
	else
	{
		ti-=re1;
		ti=ti%(p+b);
		if(ll1==0) a=p;
		else a=b;
		if(ti<a)
		{
			re1=a-ti;
			ll1=(ll1+1)%2;
		}
		else
		{
			re1=b+p-ti;
		}
	}

	ti=tt;
	b=du[to][0];
	p=du[to][1];
	ll2=light[to];
	re2=remaind[to];
	if(ti<re2)
	{
		re2=re2-ti;
	}
	else
	{
		ti-=re2;
		ti=ti%(p+b);
		if(ll2==0) a=p;
		else a=b;
		if(ti<a)
		{
			re2=a-ti;
			ll2=(ll2+1)%2;
		}
		else
		{
			re2=b+p-ti;
		}
	}

	//到这里求出时间ti时，from点和to点的灯的颜色和剩余时间
	
	if(ll1==ll2)   //如果颜色相同则返回走路的时间
		return G.gra[from][to];
	else if(re1!=re2) //如果颜色不同，灯改变颜色的剩余时间不同
	{					//返回两者较小的＋走路时间
		a=re1;
		if(re2<re1)
			a=re2;
		return a+G.gra[from][to];
	}
	else //如果剩余时间相同，两个灯的下个颜色的周期不同
	{			//返回剩余时间＋较小的周期＋走路时间
		ll1=(ll1+1)%2;
		ll2=(ll2+1)%2;
		if(du[from][ll1]!=du[to][ll2])
		{
			a=du[from][ll1];
			if(du[from][ll1]>du[to][ll2])
				a=du[to][ll2];
			return a+re1+G.gra[from][to];
		}
		else  //如果下一个周期相同，再下一个周期不同
		{		//返回剩余时间＋下一个周期的时间＋再下一个周期中较小的时间＋走路时间
			ff=du[from][ll1];
			ll1=(ll1+1)%2;
			ll2=(ll2+1)%2;
			if(du[from][ll1]!=du[to][ll2])
			{
				a=du[from][ll1];
				if(du[from][ll1]>du[to][ll2])
					a=du[to][ll2];
				return ff+a+re1+G.gra[from][to];
			}
			else return -1;   //如果仍然相同，则不可以通过，返回－1
		}
	}
}


void bellman()
{
	 //单源最短路径的bellman－ford算法
	int i,j,k;
	bool sign;
	for(i=0;i<=G.vexnum;i++)
		dis[i]=MAX;
	dis[begin]=0;
	sign=true;
	for(i=1;i<=G.vexnum && sign;i++)
	{
		sign=false;
		for(j=1;j<=G.arcnum;j++)
		{
			if(dis[arc[j][0]]<MAX)
			{
				k=tim(arc[j][0],arc[j][1],dis[arc[j][0]]);
				if(dis[arc[j][1]]>dis[arc[j][0]]+k)
				{
					dis[arc[j][1]]=dis[arc[j][0]]+k;
					sign=true;
				}
			}
		}
	}
}


int main()
{
	int i,k,m,n;
	int b,e,v;
	char s[5];
	int po,cb,cp;

	scanf("%d%d",&begin,&end);
	scanf("%d%d",&n,&m);
	memset(&G,0,sizeof(graph));
	G.vexnum=n;
	G.arcnum=2*m;
	for(i=1;i<=n;i++)
	{
		scanf("%s%d%d%d",s,&po,&cb,&cp);
		if(s[0]=='B') light[i]=0;
		else light[i]=1;
		remaind[i]=po;
		du[i][0]=cb;
		du[i][1]=cp;
	}
	k=1;
	for(i=0;i<m;i++)
	{
		scanf("%d%d%d",&b,&e,&v);
		arc[k][0]=b;
		arc[k][1]=e;
		G.gra[b][e]=v;
		k++;
		arc[k][0]=e;
		arc[k][1]=b;
		G.gra[e][b]=v;
		k++;
	}
	bellman();
	if(dis[end]==MAX)
		printf("0\n");
	else
		printf("%d\n",dis[end]);
	return 0;
}

• 自己解答 (3445) HouXran 2007-08-07 23:23:10