• <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)  編輯 收藏 引用

            无码日韩人妻精品久久蜜桃| 亚洲欧美国产日韩综合久久| 狠狠色丁香久久综合婷婷| 久久se精品一区精品二区| 亚洲精品tv久久久久| 久久发布国产伦子伦精品| 久久久噜噜噜久久| 久久99精品久久久久久久不卡 | 99热都是精品久久久久久| 香港aa三级久久三级老师2021国产三级精品三级在 | 久久久久亚洲AV片无码下载蜜桃 | 一本大道久久a久久精品综合| 亚洲欧美一区二区三区久久| 欧洲人妻丰满av无码久久不卡| www.久久热.com| 亚洲精品美女久久久久99| 麻豆久久| 国产综合精品久久亚洲| 国产精品久久波多野结衣| 久久综合亚洲色一区二区三区| 色综合久久久久网| AV色综合久久天堂AV色综合在| 亚洲午夜精品久久久久久app| AA级片免费看视频久久| 久久九九全国免费| 欧美精品一本久久男人的天堂| 久久91精品久久91综合| 久久国产色AV免费看| 无码国内精品久久人妻蜜桃| 国内精品伊人久久久影院| 狠狠色丁香久久婷婷综合蜜芽五月 | 99精品国产在热久久 | 久久99精品九九九久久婷婷| 久久久精品免费国产四虎| 精品999久久久久久中文字幕| 国产美女久久精品香蕉69| 99久久无码一区人妻a黑| .精品久久久麻豆国产精品 | 久久国内免费视频| 久久亚洲2019中文字幕| 亚洲国产天堂久久综合|