巢穴

about:blank

P1860

Bellman-Ford
看题看了半天..
#include <iostream>
#include <vector>
#include <fstream>
using namespace std;

//ifstream fin("t1860.in");
struct node
{
 int u,v;
 double r,c;
};
vector<node> edge_vec;
int n,m,s;
int f;
#define eps 1e-8
double v;
double dist[200];
void relax(int x,int y,double r,double c)
{
     if (dist[y]+eps<(dist[x]-c)*r)
        {f=1;dist[y]=(dist[x]-c)*r;}
}
bool bellman()
{
     for (int i=1;i<=n;i++)
        dist[i]=0;
     dist[s]=v;
    
    while(dist[s]<=v+eps)
    {
     f=0;
     for (int j=0;j<edge_vec.size();j++)
     {
         node edge=edge_vec.at(j);
         relax(edge.u,edge.v,edge.r,edge.c);    
     }
     if (!f) break;
    }
   if (dist[s]>v+eps) return true;
         else return false;
    
}
int main()
{
    cin>>n>>m>>s>>v;
    for (int i=1;i<=m;i++)
    {
        int x,y;
        double rxy,cxy,ryx,cyx;
        cin>>x>>y>>rxy>>cxy>>ryx>>cyx;
        node edge;
        edge.u=x;
        edge.v=y;
        edge.r=rxy;
        edge.c=cxy;
        edge_vec.push_back(edge);
        edge.u=y;
        edge.v=x;
        edge.r=ryx;
        edge.c=cyx;
        edge_vec.push_back(edge);
        
    }
        
    if (bellman()) cout<<"YES"<<endl;
       else
           cout<<"NO"<<endl;
  // system("pause");
    return 0;
}

posted on 2009-10-04 17:23 Vincent 阅读(145) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航:   博客园   博客园最新博文   博问   管理