• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            巢穴

            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 閱讀(121) 評論(0)  編輯 收藏 引用

            91精品国产乱码久久久久久| 久久99国产精品久久99果冻传媒 | 国产精品99久久久久久www| 亚洲乱码精品久久久久..| 伊人久久精品无码av一区| 无码人妻精品一区二区三区久久| 久久精品天天中文字幕人妻| 国产2021久久精品| 成人综合久久精品色婷婷| 久久久久久久人妻无码中文字幕爆| 99精品久久久久中文字幕| 久久亚洲av无码精品浪潮| 国产成人精品久久| 久久久久一区二区三区| 一级做a爰片久久毛片免费陪| 亚洲狠狠婷婷综合久久蜜芽| 久久婷婷五月综合成人D啪| 久久婷婷五月综合97色一本一本| 精品久久久久久国产牛牛app | 久久夜色精品国产欧美乱| 国产精品福利一区二区久久| 一级A毛片免费观看久久精品| 久久精品人人做人人爽电影| 欧美激情一区二区久久久| 久久综合九色综合精品| 日韩人妻无码精品久久久不卡| 国内精品久久久久久久久电影网 | 亚洲国产日韩欧美久久| 久久精品国产一区二区三区日韩| 久久久无码精品亚洲日韩京东传媒 | 精品久久久久久久无码| 久久精品中文字幕一区| 91精品国产高清久久久久久国产嫩草 | 国产A三级久久精品| 日批日出水久久亚洲精品tv| 国内精品久久久久久麻豆 | 99精品久久久久久久婷婷| 久久亚洲国产中v天仙www | 九九99精品久久久久久| 国产成人久久精品一区二区三区| 老色鬼久久亚洲AV综合|