#include<cstdio>
int s, n, m, i, j, d[222][2], f;
double v, c[222][2], x[111];
int man()
{
	x[s] = v;
	for (i = 1; i < n; i++)
	{
		f = 0;
		for (j = 0; j < 2 * m; j++)
			if (x[d[j][1]] < (x[d[j][0]] - c[j][1])*c[j][0])
				f = 1, x[d[j][1]] = (x[d[j][0]] - c[j][1])*c[j][0];
		if (!f)   return 0;
	}
	for (j = 0; j < 2 * m; j++)
		if (x[d[j][1]] < (x[d[j][0]] - c[j][1])*c[j][0])
			return 1;
	return 0;
}
int main()
{
	scanf("%d%d%d%lf", &n, &m, &s, &v);
	for (i = 0; i < m; i++)
		scanf("%d%d%lf%lf%lf%lf", &d[2 * i][0], &d[2 * i][1], &c[2 * i][0], &c[2 * i][1], &c[2 * i + 1][0], &c[2 * i + 1][1]), d[2 * i + 1][0] = d[2 * i][1], d[2 * i + 1][1] = d[2 * i][0];
	puts(man() ? "YES" : "NO");
}

• Re:贴一发Bellman-Ford的0ms精简代码~ (11) forestgump2012 2022-02-12 21:39:09