POJ 1860 Currency Exchange——spfa判正环

POJ 1860 Currency Exchange——spfa判正环

dis初始化为0，dis[S] = V, 松弛操作为if (dis [u]  < (dis[v] - c) * v) dis [u]  = (dis[v] - c) * v,结束条件为dis[S] > V

#include #include #include #include #include #include using namespace std;const int INF = 0x3f3f3f3f;const int maxn = 1010;bool vis[maxn];int N, M, S;double V, dis[maxn];struct Date { int x; double C, R; Date(int xx, double cc, double rr) : x(xx), C(cc), R(rr) {}};vector G[maxn];bool spfa() { for (int i = 1; i <= N; i++) dis[i] = 0, vis[i] = false; dis[S] = V, vis[S] = true; queue q; q.push(S); while (!q.empty()) { int u = q.front(); q.pop(); vis[u] = false; for (int i = 0; i < G[u].size(); i++) { int v = G[u][i].x; double c = G[u][i].C, r = G[u][i].R; if (dis[v] < (dis[u] - c) * r) { dis[v] = (dis[u] - c) * r; if (!vis[v]) vis[v] = true, q.push(v); } } if (dis[S] > V) return true; } return false;}int main() { int u, v; double C1, R1, C2, R2; while (~scanf("%d %d %d %lf", &N, &M, &S, &V)) { for (int i = 1; i <= N; i++) G[i].clear(); while (M--) { scanf("%d %d %lf %lf %lf %lf", &u, &v, &R1, &C1, &R2, &C2); G[u].push_back(Date(v, C1, R1)); G[v].push_back(Date(u, C2, R2)); } if(spfa()) printf("YES\n"); else printf("NO\n"); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。