• <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>
            隨筆 - 87  文章 - 279  trackbacks - 0
            <2025年7月>
            293012345
            6789101112
            13141516171819
            20212223242526
            272829303112
            3456789

            潛心看書研究!

            常用鏈接

            留言簿(19)

            隨筆分類(81)

            文章分類(89)

            相冊

            ACM OJ

            My friends

            搜索

            •  

            積分與排名

            • 積分 - 217972
            • 排名 - 117

            最新評論

            閱讀排行榜

            評論排行榜

             原來用stl的優(yōu)先隊列這么爽,比賽時候多用,heap太容易打錯了,畢竟沒ghost_wei那么bt(heap,就幾行,都打爛了-_-)

            pku3159:

            #include <iostream>
            #include 
            <vector>
            #include 
            <queue>
            using namespace std;

            const int INF = 1 << 28;
            const int MAXN = 30010;

            struct PQNode {
                
            int u, key;
                
            //pq默認(rèn)用<判斷優(yōu)先級,key大優(yōu)先,若要key小優(yōu)先,則加上!或<改成>即可
                friend bool operator<(const PQNode &a, const PQNode &b) return !(a.key < b.key); } 
                
            }
            ;


            int n, m;
            vector
            <int> adjv[MAXN], adjw[MAXN];

            int dijkstraPQ(int st, int en) {
                
            int i, v, w, dist[MAXN], chk[MAXN];
                priority_queue
            <PQNode> pq;
                PQNode tmp, cp;

                memset(chk, 
            0sizeof(chk));
                
            for (i=0; i<n; i++) dist[i] = INF;

                dist[st] 
            = 0
                tmp.u 
            = st; tmp.key = 0;
                pq.push(tmp);
                
            while (!pq.empty()) {
                    cp 
            = pq.top();
                    pq.pop();
                    
            if (cp.u == en) return dist[en];
                    
            if (chk[cp.u]) continue;
                    chk[cp.u] 
            = 1;
                    
            for (i=0; i<adjv[cp.u].size(); i++{
                        v 
            = adjv[cp.u][i]; w = adjw[cp.u][i];
                        
            if (!chk[v] && (dist[v]==INF || dist[v]>cp.key+w)) {
                            dist[v] 
            = cp.key+w;
                            tmp.u 
            = v; tmp.key = dist[v];
                            pq.push(tmp);
                        }

                    }

                }

                
            return -1;
            }


            int main() {
                
            int i, j, k, u, v, w;
                freopen(
            "input.txt""r", stdin);
                scanf(
            "%d%d"&n, &m);
                
            for (i=0; i<m; i++{
                    scanf(
            "%d%d%d"&u, &v, &w);
                    u
            --; v--;
                    adjv[u].push_back(v);
                    adjw[u].push_back(w);
                }

                printf(
            "%d\n", dijkstraPQ(0, n-1));
                
            return 0;
            }


            posted on 2007-11-03 16:40 閱讀(1334) 評論(4)  編輯 收藏 引用 所屬分類: 算法&ACM

            FeedBack:
            # re: 用stl打spfa短了1k代碼,慢了200ms 2007-11-07 20:01 wei
            總結(jié)了很多ACM ~,牛~,佩服!
            有沒有資料傳我一份,THANKS。。。
            郵箱 amyvmiwei@126.com
            謝謝!  回復(fù)  更多評論
              
            # re: 用stl打spfa短了1k代碼,慢了200ms 2008-03-31 11:02 AC_Tekkaman
            TLE..  回復(fù)  更多評論
              
            # re: 用stl打spfa短了1k代碼,慢了200ms 2009-03-27 22:46 KR
            擺明的隊列dij。。。。
              回復(fù)  更多評論
              
            # re: 用stl打spfa短了1k代碼,慢了200ms 2010-02-18 02:29 路過
            這不是SPFA喔...  回復(fù)  更多評論
              
            亚洲精品97久久中文字幕无码| 大香伊人久久精品一区二区| 国产午夜福利精品久久2021 | 国内精品伊人久久久久| 国内精品久久久久影院优| 精品视频久久久久| 久久亚洲国产成人影院网站| 欧美激情一区二区久久久| 久久婷婷五月综合国产尤物app| 久久久久久a亚洲欧洲aⅴ| 久久久久99这里有精品10| 国产精品久久午夜夜伦鲁鲁| 久久久WWW免费人成精品| 亚洲AV无码久久精品蜜桃| 久久久久久久久久久免费精品| 亚洲国产精品高清久久久| 久久久久亚洲AV无码去区首| 精品久久久久久无码专区| 久久婷婷色综合一区二区| 狠狠色丁香婷婷久久综合不卡| 久久精品免费全国观看国产| 99久久综合国产精品二区| 久久精品国产亚洲精品2020| 亚洲精品第一综合99久久 | 久久这里的只有是精品23| 久久99精品久久久久久hb无码| 污污内射久久一区二区欧美日韩| 久久伊人精品青青草原高清| 日韩精品久久无码人妻中文字幕 | 日本强好片久久久久久AAA| 欧美性大战久久久久久| 99久久综合狠狠综合久久| 婷婷久久综合九色综合98| 久久精品国产第一区二区三区 | 人妻精品久久久久中文字幕69| 伊人久久大香线蕉综合网站| 久久人人爽人人澡人人高潮AV| 久久亚洲av无码精品浪潮| 久久av免费天堂小草播放| 色偷偷91久久综合噜噜噜噜| 精品熟女少妇aⅴ免费久久|