• <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>
            心如止水
            Je n'ai pas le temps
            posts - 400,comments - 130,trackbacks - 0
            SPFA判負權回路。
            以下是我的代碼:
            #include<queue>
            #include
            <cstdio>
            #include
            <cstring>
            using namespace std;
            const int kMaxn(507);
            const int kMaxm(5207);
            const long long kInf(0x7f7f7f7f7f7f7f7fll);

            struct Edge
            {
                
            int v,w;
            };

            int n,m,w;
            int cnt,first[kMaxn],next[kMaxm];Edge e[kMaxm];

            void AddEdge(int u,int v,int w)
            {
                cnt
            ++;
                e[cnt].v
            =v;e[cnt].w=w;
                next[cnt]
            =first[u];
                first[u]
            =cnt;
            }

            bool SPFA()
            {
                
            long long dist[kMaxn];
                queue
            <int> q;
                
            int num[kMaxn]={0};
                
            bool inq[kMaxn]={false};
                
            for(int i=1;i<=n;i++)
                    dist[i]
            =(i==1?0:kInf);
                q.push(
            1);
                inq[
            1]=true;
                num[
            1]++;
                
            while(!q.empty())
                {
                    
            int u(q.front());q.pop();
                    inq[u]
            =false;
                    
            if(num[u]>n)
                        
            return true;
                    
            for(int i=first[u];i!=-1;i=next[i])
                    {
                        
            int v(e[i].v),w(e[i].w);
                        
            if(dist[v]>dist[u]+w)
                        {
                            dist[v]
            =dist[u]+w;
                            
            if(!inq[v])
                            {
                                q.push(v);
                                inq[v]
            =true;
                                num[v]
            ++;
                            }
                        }
                    }
                }
                
            return false;
            }

            int main()
            {
                
            int T;
                scanf(
            "%d",&T);
                
            while(T--)
                {
                    scanf(
            "%d%d%d",&n,&m,&w);
                    cnt
            =0;
                    memset(first,
            -1,sizeof(first));
                    
            for(int i=1;i<=m;i++)
                    {
                        
            int u,v,w;
                        scanf(
            "%d%d%d",&u,&v,&w);
                        AddEdge(u,v,w);
                        AddEdge(v,u,w);
                    }
                    
            for(int i=1;i<=w;i++)
                    {
                        
            int u,v,w;
                        scanf(
            "%d%d%d",&u,&v,&w);
                        AddEdge(u,v,
            -w);
                    }

                    
            if(SPFA())
                        printf(
            "YES\n");
                    
            else
                        printf(
            "NO\n");
                }

                
            return 0;
            }
            posted on 2011-07-31 09:51 lee1r 閱讀(253) 評論(0)  編輯 收藏 引用 所屬分類: 題目分類:圖論
            国产一区二区精品久久凹凸| 久久久综合九色合综国产| 国产精品美女久久福利网站| 久久热这里只有精品在线观看| 久久久久AV综合网成人| 人妻少妇精品久久| 精品999久久久久久中文字幕| 久久久久无码精品| 潮喷大喷水系列无码久久精品| 欧美一级久久久久久久大| 久久99免费视频| 日韩精品久久无码人妻中文字幕| 久久99国产精品成人欧美| 久久青青草原亚洲av无码app| 久久国产影院| 一本一道久久精品综合| 日韩精品久久久久久久电影蜜臀| 欧美粉嫩小泬久久久久久久| 日韩亚洲欧美久久久www综合网 | 7777久久亚洲中文字幕| 一97日本道伊人久久综合影院| 国产精品久久网| 久久大香香蕉国产| 少妇人妻88久久中文字幕| 久久国语露脸国产精品电影| 欧美日韩精品久久久免费观看| 久久99精品久久久久久9蜜桃| 久久A级毛片免费观看| 精品无码久久久久久尤物| 婷婷五月深深久久精品| 99久久精品免费看国产一区二区三区 | 亚洲欧洲日产国码无码久久99| 伊人久久精品影院| 午夜福利91久久福利| 亚洲国产成人乱码精品女人久久久不卡 | 人妻无码αv中文字幕久久琪琪布 人妻无码精品久久亚瑟影视 | 国产精品久久久久影视不卡| 久久久久久狠狠丁香| 91性高湖久久久久| 久久se这里只有精品| 欧美久久一级内射wwwwww.|