#include <iostream> #include <vector> using namespace std; struct ex{ double r, c; ex() { r = 0; c = 0; } void scan() { cin >> r >> c; } double change(double a) { return (a-c)*r; } }; struct edge { int from, to; ex weight; edge(int f, int t, ex w) { from = f; to = t; weight = w; } }; int main() { int n, m, s; double money; cin >> n >> m >> s >> money; vector <edge*> edges = vector<edge*>(); //массив всех ребер int vf, vt; ex e1, e2; for (int i = 0; i < m; ++i) { cin >> vf >> vt; e1.scan();e2.scan(); edges.push_back(new edge(vf-1, vt-1, e1)); edges.push_back(new edge(vt-1, vf-1, e2)); } double dist[100]; for (int i = 0; i < n; ++i) { dist[i] = -1; } dist[s-1] = money; for (int i = 0; i < n; ++i) { for (edge* e: edges) { if (dist[e->from] > 0) { if (dist[e->to] < e->weight.change(dist[e->from])) { if (i == n-1 && dist[e->to] != -1) { cout << "YES"; return 0; } else { dist[e->to] = e->weight.change(dist[e->from]); } } } } } cout << "NO"; return 0; }解释算法

这是一个基于贝尔曼-福德算法的最短路径问题的解决方案。该算法用于解决带有负边权的图上的最短路径问题。在此解决方案中，对于每个节点，我们都计算了它到源节点的最短路径。然后，我们使用从源节点出发的所有边来更新从源节点到其它节点的最短路径。我们重复这个过程，直到我们不能再更新任何路径或我们已经进行了 N 次迭代（其中 N 是节点数）。如果在 N 次迭代后仍然可以更新任何路径，则存在一个负环，我们可以通过这个负环来无限次减少路径的长度。在此解决方案中，我们使用结构体存储边的权重，它包含两个值：r 和 c。它们分别代表汇率和费用。