POJ1789-SPFA

此题要注意松弛条件

 

#include<iostream>
#include<queue>
using namespace std;
#define MAXSIZE 1000
typedef struct node{
	int u;
	int v;
	double w;
	double c;
}node;
node p[MAXSIZE];
int head[MAXSIZE];
int next[MAXSIZE];
int n,m,s;
double dis[MAXSIZE];
double v;//v 为初始拥有的货币数量
int e;
queue<int>que;
int vis[MAXSIZE];
int cnum[MAXSIZE];

int spfa(int s)
{
	int i,j;
	while(!que.empty())
		que.pop();
	memset(vis,0,sizeof(vis));
	memset(cnum,0,sizeof(cnum));
	memset(dis,0,sizeof(dis));//初始时每个节点都没有钱
	vis[s]=1;
	cnum[s]++;
	dis[s]=v;
	que.push(s);
	while(!que.empty())//当队列非空
	{
		int te=que.front();
		que.pop();
		vis[te]=0;
		for(i=head[te];i!=-1;i=next[i])//取出te相连的所有点
		{
			//if 利益增加了 则松弛（对应于 路径变短）
			//（现在拥有的货币-手续费）*比率 等于可以换得的货币
			double tt=(dis[te]-p[i].c)*p[i].w;//dis[te] 表示te这个点拥有的资产
			if(dis[p[i].v]<tt)
			{
				dis[p[i].v]=tt;
				if(!vis[p[i].v])
				{
					vis[p[i].v]=1;
					cnum[p[i].v]++;
					que.push(p[i].v);
					if(cnum[p[i].v]>n)
					{
						return 1;
					}
				}
			}
		}
	}
	
	return 0;
}


void addnode(int u,int v,double w,double c)
{
	p[e].u=u;
	p[e].v=v;
	p[e].w=w;
	p[e].c=c;
	next[e]=head[u];
	head[u]=e++;
}
int main()
{
	//freopen("in.txt","r",stdin);
	//while(scanf("%d%d%d%lf",&n,&m,&s,&v)!=EOF)
	{
		scanf("%d%d%d%lf",&n,&m,&s,&v);
		e=0;
		memset(head,-1,sizeof(head));
		memset(next,-1,sizeof(next));
		while(m--)
		{	
			int a,b;
			double r1,c1,r2,c2;
			scanf("%d%d%lf%lf%lf%lf",&a,&b,&r1,&c1,&r2,&c2);
			addnode(a,b,r1,c1);
			addnode(b,a,r2,c2);
		}
		//spfa
		if(spfa(s))
			printf("YES\n");
		else
			printf("NO\n");

	}
}