spfa
C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int N = 240;
int h[N], e[N], ne[N], idx;
double r[N], c[N];
int cnt[N];
int n, m, s;
double v;
double dist[N];
bool st[N];
inline void add(int a, int b, double x, double y)
{
e[idx] = b, r[idx] = x, c[idx] = y, ne[idx] = h[a], h[a] = idx ++;
}
inline bool spfa()
{
queue<int> q;
q.push(s);
dist[s] = v;
st[1] = true;
while (q.size())
{
auto t = q.front();
q.pop();
st[t] = false;
for (int i = h[t]; ~i; i = ne[i])
{
int j = e[i];
if (dist[j] < (dist[t] - c[i]) * r[i])
{
dist[j] = (dist[t] - c[i]) * r[i];
cnt[j] = cnt[t] + 1;
if (cnt[j] >= n) return true;
if (!st[j])
{
q.push(j);
st[j] = true;
}
}
}
}
return false;
}
inline void solve()
{
cin >> n >> m >> s >> v;
memset(h, -1, sizeof h);
while (m -- )
{
int a, b;
double x1, y1, x2, y2;
cin >> a >> b >> x1 >> y1 >> x2 >> y2;
add(a, b, x1, y1), add(b, a, x2, y2);
}
if (spfa()) puts("YES");
else puts("NO");
}
int main()
{
cin.tie(nullptr) -> sync_with_stdio(0);
solve();
return 0;
}