題意：幣種兌換尋找是否有正環(huán)
計算公式 （money - Cost) * Rate
思路:spfa_dfs 判正環(huán)
#include<stdio.h>
#include<string.h>
#include <vector>
using namespace std;
const int MAX_V = 200;
struct edge {int to;
double Rate,C;};
vector<edge> G[MAX_V];
bool instack[MAX_V];
double d[MAX_V];
int V;
bool spfa_dfs(int s){
instack[s] = true;
for (int i = 0;i<G[s].size();i++){
edge e = G[s][i];
if (d[e.to] < (d[s] -e.C) * e.Rate){
d[e.to] = (d[s] - e.C) * e.Rate;
if (!instack[e.to]){
if (spfa_dfs(e.to)) return true;
} else{
return true;
}
}
}
instack[s] = false;
return false;
}
int main()
{
double money;
int M,S;
scanf("%d%d%d%lf",&V,&M,&S,&money);
for (int i = 0;i<M;i++){
int u,v;
double Ruv,Cuv,Rvu,Cvu;
scanf("%d%d%lf%lf%lf%lf",&u,&v,&Ruv,&Cuv,&Rvu,&Cvu);
G[u].push_back(edge{v,Ruv,Cuv});
G[v].push_back(edge{u,Rvu,Cvu});
}
memset(d,0,sizeof d);
memset(instack,0,sizeof instack);
d[S] = money;
if (spfa_dfs(S))
printf("YES\n");
else
printf("NO\n");
return 0;
}
