算法：
1.SPFA求最长路，dis【】初始直为0，大于改成小于号
2.松弛结束后，判断是否大于dis[S] > V， 大于就输出YES， 否则输出NO
View Code #include#include #include #include #include #include #define MAXN 100100using namespace std;struct Edge{ int u, next; double val, cost; Edge( ) { } Edge( int U, int Next, double Val, double Cost): u(U), next(Next), val(Val), cost(Cost) {}}edge[MAXN];int N, M, S, head[MAXN], visit[MAXN], hash[MAXN], size;double V, dis[MAXN];struct node{ int ID; // double rate; double money; // double c;};void init( ){ for( int i = 0; i < MAXN; i++) { head[i] = -1; dis[i] = 0; visit[i] = 0; hash[i] = 0; } size = 0; }void AddEdge( int u, int v, double val1, double val2, double Cost1, double Cost2){ edge[size] = Edge( v, head[u], val1, Cost1); head[u] = size++; edge[size] = Edge( u, head[v], val2, Cost2); head[v] = size++; }void SPFA( ){ queue q; node p; p.ID = S; p.money = V; q.push( p ); dis[S] = V; hash[S] = 1; while( !q.empty()) { p = q.front( ); q.pop( ); int v = p.ID; double money = dis[v]; visit[v] = 0; for( int e = head[v]; e != -1; e = edge[e].next) { int v = edge[e].u; double rate = edge[e].val; double cost = edge[e].cost; double xx = rate * ( money - cost ); if( dis[v] < xx ) { dis[v] = xx; if( !visit[v] ) { p.ID = v; p.money = dis[v]; q.push( p ); visit[v] = 1; hash[v]++; } } } } if( fabs(dis[S]) - V > 0 ) puts("YES"); else puts("NO"); }int main( ){ int a, b; double rab, cab, rba, cba; while( scanf("%d%d%d%lf",&N, &M, &S, &V) != EOF) { init( ); for( int i = 1; i <= M; i++) { scanf("%d%d%lf%lf%lf%lf",&a, &b, &rab, &cab, &rba, &cba); AddEdge( a, b, rab, rba, cab, cba); } SPFA( ); } return 0; }