题意:有多个银行可以换钱,每个银行可以将特定的两种钱相互兑换,并且有自己的汇率,现在问是否可以将自己的钱通过银行兑换增加。
其实比较水,主要就是知道最短路问题里的负环可以通过bellman-fold或spfa判断出来,在这里其实就是找正的环就行了。
一开始WA了无数发……原因是传参传了int,但其实是double……
#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std; int head[],point[],next[],size,t[],n,m;
double r[],c[],dist[];
bool vis[]; void add(int a,int b,double r1,double c1){
point[size]=b;
r[size]=r1;
c[size]=c1;
next[size]=head[a];
head[a]=size++;
} void spfa(int s,double v){
int i;
memset(dist,,sizeof(dist));
memset(vis,,sizeof(vis));
memset(t,,sizeof(t));
dist[s]=v;
queue<int>q;
q.push(s);
vis[s]=;
bool f=;
while(!q.empty()){
if(f)break;
int u=q.front();
q.pop();
vis[u]=;
for(i=head[u];~i;i=next[i]){
int j=point[i];
if(dist[j]<(dist[u]-c[i])*r[i]){
dist[j]=(dist[u]-c[i])*r[i];
if(!vis[j]){
q.push(j);
vis[j]=;
t[j]++;
if(t[j]>n)f=;
}
}
}
}
if(f)printf("YES\n");
else printf("NO\n");
} int main(){
int s,i;
double v;
while(scanf("%d%d%d%lf",&n,&m,&s,&v)!=EOF){
memset(head,-,sizeof(head));
size=;
for(i=;i<=m;i++){
int a,b;
double r1,c1;
scanf("%d%d%lf%lf",&a,&b,&r1,&c1);
add(a,b,r1,c1);
scanf("%lf%lf",&r1,&c1);
add(b,a,r1,c1);
}
spfa(s,v);
}
return ;
}