• <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香蕉| 国产ww久久久久久久久久| 久久综合精品国产一区二区三区| 亚洲午夜精品久久久久久浪潮| 亚洲va中文字幕无码久久不卡| 欧美国产精品久久高清| 四虎国产精品成人免费久久| 久久人人爽人人爽人人片AV东京热| 亚洲精品无码成人片久久| 九九99精品久久久久久| 亚洲午夜久久久| 国产午夜精品理论片久久影视| 97久久精品人妻人人搡人人玩| 少妇精品久久久一区二区三区 | 久久精品九九亚洲精品| 麻豆一区二区99久久久久| 激情久久久久久久久久| 久久久亚洲欧洲日产国码二区| 青春久久| 久久久久久久尹人综合网亚洲| 亚洲精品国产自在久久| 国产Av激情久久无码天堂| 久久亚洲国产精品成人AV秋霞 | 国内精品久久久久影院薰衣草 | 香港aa三级久久三级老师2021国产三级精品三级在 | 久久久受www免费人成| AV色综合久久天堂AV色综合在 | 丰满少妇人妻久久久久久| 18岁日韩内射颜射午夜久久成人| 久久国产精品成人影院| 思思久久精品在热线热| 开心久久婷婷综合中文字幕| 伊人久久大香线焦综合四虎| 久久婷婷五月综合色高清| 囯产精品久久久久久久久蜜桃| 久久91精品国产91久| 久久一区二区三区99| 韩国三级中文字幕hd久久精品| 久久久久国产亚洲AV麻豆| 精品一区二区久久久久久久网站| 国产精品免费久久久久电影网|