• <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

            P1062

            WA了多次.因為構(gòu)圖時少打了個=號....
            枚舉最高rank,多次構(gòu)圖,然后就最短路 O(N^3)

            以后要注意靜態(tài)調(diào)試
            #include <iostream>
            //#include <fstream>
            #include <math.h>
            using namespace std;

            //ifstream fin("t1062.in");


            const int MAXN=101;
            #define INF 2147483647
            int p[MAXN],l[MAXN],x;
            int u[MAXN][MAXN];
            int q[MAXN];
            int m,n;

            void dijkstra()
            {
                 
            int dist[MAXN];
                 
            bool hash[MAXN];
                 
            int answer=INF;
                 
            for (int i=n;i>=1;--i)
                 
            {
                  
            int maxRank=l[i];
                  
            for (int j=1;j<=n;++j)
                      
            if (l[j]>maxRank||maxRank-l[j]>m) q[j]=1;
                      
            else q[j]=0;
                  memset(hash,
            0,sizeof(hash));
                  
            for (int j=1;j<=n;++j)
                      dist[j]
            =p[j];
                  
            for (int j=1;j<=n;++j)
                  
            {
                   
            int u1=0;
                   
            int min=INF;
                   
            for (int k=1;k<=n;++k)
                   
            {
                    
            if (q[k]) continue;
                    
            if (hash[k]) continue;
                    
            if (min>dist[k])    {min=dist[k];u1=k;}
                    
                   }

                   hash[u1]
            =true;
                   
            if (u1==0break;
                   
            if (dist[u1]==0x7fbreak;
                   
            for (int k=1;k<=n;++k)
                   

                       
            if (q[k]) continue;
                       
            if (u[u1][k]==0x7fcontinue
                       
            if (dist[k]>dist[u1]+u[u1][k])
                       
            {
                        dist[k]
            =dist[u1]+u[u1][k];
                       }

                   }

                  }

                  
            if (answer>dist[1]) answer=dist[1];
                 }

                 cout
            <<answer<<endl;

            }

            int main()
            {
                memset(u,
            0x7f,sizeof(u));
                cin
            >>m>>n;
                
            for (int i=1;i<=n;i++)
                
            {
                    cin
            >>p[i]>>l[i]>>x;
                    
            for (int j=1;j<=x;j++)
                    
            {
                        
            int t,v;
                        cin
            >>t>>v;
                        u[t][i]
            =v;
                    }

                }

                dijkstra();
                
            return 0;
            }

            posted on 2009-10-05 09:23 Vincent 閱讀(102) 評論(0)  編輯 收藏 引用 所屬分類: 數(shù)據(jù)結(jié)構(gòu)與算法

            青青草原综合久久大伊人精品| 久久影院亚洲一区| 少妇内射兰兰久久| 久久九九青青国产精品| 中文字幕一区二区三区久久网站| 久久97久久97精品免视看| 欧美久久久久久精选9999| 97精品伊人久久久大香线蕉| 久久精品9988| 亚洲天堂久久久| 日本精品久久久久中文字幕8| 久久国产精品波多野结衣AV| 亚洲午夜久久久久久久久久| 热久久国产精品| 久久精品水蜜桃av综合天堂| 久久久久人妻一区精品果冻| 精品久久久久久成人AV| 超级碰碰碰碰97久久久久| 日韩精品国产自在久久现线拍 | 午夜欧美精品久久久久久久| 91久久精品国产免费直播| 欧洲精品久久久av无码电影| 青青草原综合久久大伊人导航| 99久久中文字幕| 久久午夜羞羞影院免费观看| 久久人人青草97香蕉| 久久综合色之久久综合| 精品久久人人做人人爽综合| 久久99精品国产| 久久男人Av资源网站无码软件 | 中文精品99久久国产| 久久久久无码国产精品不卡| 99久久精品国产毛片| 热re99久久精品国产99热| MM131亚洲国产美女久久| 精品国际久久久久999波多野| 久久久久高潮综合影院| 亚洲日本久久久午夜精品| 怡红院日本一道日本久久 | 久久久午夜精品| 精品久久久久久久久免费影院|