#include<cstdio>
#include<queue>
#define MN 2000
#define ME 20000
using std::queue;
#define UNCONN -1.0
struct  
{
	int to;
	int pre;
	double rate;
	double commission;
}edge[ME];
int box[MN];
int lenE;
void iniPreList(int n)
{
	int i;
	for(i=0;i<=n;i++)
	{
		box[i] = UNCONN;
	}
	lenE = 0;
}
void addDirectedEdge(int frm,int to,double rate,double commission)
{
	edge[lenE].to = to;
	edge[lenE].rate = rate;
	edge[lenE].commission = commission;
	edge[lenE].pre = box[frm];
	box[frm] = lenE++;
}
void addDoubleEdge(int a,int b,double rate,double commission)
{
	addDirectedEdge(a,b,rate,commission);
	addDirectedEdge(b,a,rate,commission);
}
bool isNotInQueue[MN];
double money[MN];
int cntRelax[MN];
class node
{
public:
	int to;
	double w;
	node(int tt,double ww):to(tt),w(ww){}
};
bool spfa(double mymoney,int start,int destination,int n)
{
	//初始化
	int i;
	for(i=1;i<=n;i++)
	{
		isNotInQueue[i] = true;
		money[i] = UNCONN;
		cntRelax[i]=0;
	}
	money[start] = mymoney;
	node cur(start,mymoney);
	queue<node> dq;
	int adsIndex;
	double tmpMoney;
	dq.push(cur);
	isNotInQueue[cur.to] = false;
	while(!dq.empty())
	{
		cur = dq.front();
		dq.pop();
		isNotInQueue[cur.to] = true;
		for(adsIndex = box[cur.to];adsIndex!=-1;adsIndex=edge[adsIndex].pre)
		{
			tmpMoney = (cur.w-edge[adsIndex].commission) * edge[adsIndex].rate;
			if(money[edge[adsIndex].to]==UNCONN||money[edge[adsIndex].to]<tmpMoney)
			{
				money[edge[adsIndex].to] = tmpMoney;
				if(isNotInQueue[edge[adsIndex].to])
				{
					dq.push(node(edge[adsIndex].to,money[edge[adsIndex].to]));
					isNotInQueue[edge[adsIndex].to] = false;
				}
				cntRelax[edge[adsIndex].to]++;
				if(cntRelax[edge[adsIndex].to]>n)//无向图产生了正环
				{
					return true;
				}
				if(edge[adsIndex].to==destination&&tmpMoney-mymoney>0.001)//已经比起始点大了
				{
					return true;
				}
			}		
		}
	}
	return false;
}
int main()
{
	int n,m,s;
	double v;
	int i;
	int a,b;
	double r1,c1,r2,c2;
	while(~scanf("%d%d%d%lf",&n,&m,&s,&v))
	{
		//读图部分
		iniPreList(n);
		for(i=0;i<m;i++)
		{
			scanf("%d%d%lf%lf%lf%lf",&a,&b,&r1,&c1,&r2,&c2);
			addDirectedEdge(a,b,r1,c1);
			addDirectedEdge(b,a,r2,c2);
		}
		if(spfa(v,s,s,n))
		{
			printf("YES\n");
		}
		else
		{
			printf("NO\n");
		}
	}
	return 0;
}

• Re:求路过的大侠帮忙看看spfa错哪了 (2602) hzl88888888 2012-07-04 16:17:11
  • Re:求路过的大侠帮忙看看spfa错哪了 (14) hzl88888888 2012-07-04 16:18:09