poj1860

刚上来一堆英文着实有点蒙逼，仔细分析是一个Bellman的变形，只要能找出一个无限增大的环这个题就好解决了，我这里用的SPFA，用邻接链表进行储存，直接套用的模板，部分变量名字没有改的很好

#include <iostream>

#include<string.h>

#include <queue>

#include <vector>

using namespace std;

#define MAX  99999999;

double dis[1000+6];

double vis[1000+6];

int n;

double fir;

typedef struct

{

	int x;

	double rate;

	double cost;

}point;

vector<point> p[1010];

int Spfa(int start)

{

    queue<int> Q;

    memset(vis, 0, sizeof(vis));

    memset(dis, 0, sizeof(dis));

    dis[start] = fir;

    vis[start] = true;

    Q.push(start);

    while (!Q.empty()){

        int temp = Q.front();

        Q.pop();

         vis[temp] = false;

        for(int i=0; i<p[temp].size(); i++)

        {

            int v=p[temp][i].x;

            double w=p[temp][i].rate;

            double z=p[temp][i].cost;

            if ((dis[temp]-z)*w > dis[v])

            {

                dis[v] = (dis[temp]-z)*w;

                if(dis[start]>fir)

                    return true;

                if (!vis[v])

                {

                    Q.push(v);

                    vis[v] = true;

                }

            }

        }

    }

    return false;

}

int main()

{

    int m,s;

    while(cin>>n>>m>>s>>fir)

    {

        point node;

       int from,to;

       double rab,rba,cab,cba;

       for(int i=0;i<m;i++)

       {

           cin>>from>>to>>rab>>cab>>rba>>cba;

           node.x=to;

           node.rate=rab;

           node.cost=cab;

           p[from].push_back(node);

           node.x=from;

           node.rate=rba;

           node.cost=cba;

           p[to].push_back(node);

       }

       int flag=0;

       flag=Spfa(s);

       if(flag)

       cout<<"YES"<<endl;

       else

       cout<<"NO\n";

    for(int i=1;i<n;i++)

        p[i].clear();

    }

    return 0;

}