> #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错哪了 (14) hzl88888888 2012-07-04 16:18:09