• <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>
            單源最短路 Dijkstra O(mlogn) (類實現(xiàn))

            #include <iostream>
            #include 
            <vector>
            #include 
            <map>

            #define maxn 1010
            using namespace std;
            typedef 
            double weight;

            class graph_c
            {
            public:
                
            void init(int _n);
                
            void dijkstra(int S);
                
            void add_edge(int u, int v, weight w);
            private:
                
            int n;
                vector 
            <int> r[maxn];
                vector 
            <weight> e[maxn];
                weight dist[maxn];
                
            int pa[maxn];
                multimap 
            <weight, int> h;
            }
            ;

            void graph_c::init(int _n)
            {
                n 
            = _n;
                
            for (int i = 0; i < n; i++)
                
            {
                    r[i].clear();
                    e[i].clear();
                }

            }


            void graph_c::add_edge(int u, int v, weight w)
            {
                r[u].push_back(v);
                e[u].push_back(w);
            }


            void graph_c::dijkstra(int S)
            {
                weight d, tmp;
                
            int v;
                multimap
            <weight, int>::iterator it;
                h.clear();
                
            for (int i = 0; i < n; i++) dist[i] = -1;
                dist[S] 
            = 0;
                pa[S] 
            = -1;
                h.insert(multimap
            <weight, int>::value_type(0, S));
                
            while (!h.empty())
                
            {
                    it 
            = h.begin();
                    v 
            = it->second;
                    d 
            = it->first;
                    h.erase(it);
                    
            for (int i = 0; i < r[v].size(); i++)
                    
            {
                        tmp 
            = d + e[v][i];
                        
            int j = r[v][i];
                        
            if (dist[j] < 0 || tmp < dist[j])
                        
            {
                            dist[j] 
            = tmp;
                            pa[j] 
            = v;
                            h.insert(multimap
            <weight, int>::value_type(tmp, j));
                        }

                    }

                }

            }
            posted on 2007-08-13 10:01 Felicia 閱讀(832) 評論(1)  編輯 收藏 引用 所屬分類: Felicia 的標程圖論
            Comments
            • # re: 單源最短路 Dijkstra O(mlogn) (類實現(xiàn))
              KR
              Posted @ 2009-03-22 22:46
              確實精彩  回復  更多評論   
             
            欧美一区二区三区久久综| WWW婷婷AV久久久影片| 亚洲精品97久久中文字幕无码| 久久国产香蕉视频| 久久综合亚洲鲁鲁五月天| 精品久久久久久国产| 999久久久无码国产精品| 97久久精品人人澡人人爽| 一本久道久久综合狠狠躁AV| 无码人妻精品一区二区三区久久久| 99999久久久久久亚洲| 亚洲欧洲中文日韩久久AV乱码| 国内高清久久久久久| 久久婷婷五月综合色奶水99啪| 91精品国产91久久久久福利| 久久伊人色| 久久人人妻人人爽人人爽| 久久综合欧美成人| 久久国产亚洲精品| 久久久久夜夜夜精品国产| 国产毛片久久久久久国产毛片 | 久久久久一级精品亚洲国产成人综合AV区| 亚洲伊人久久综合中文成人网| 996久久国产精品线观看| 无码任你躁久久久久久老妇| 精品久久久久久久| 久久亚洲精品成人AV| 久久婷婷色综合一区二区| 国产精品狼人久久久久影院| 青青草原精品99久久精品66| 日日狠狠久久偷偷色综合免费| 狠狠色丁香婷综合久久| 久久综合九色综合网站| 久久这里有精品| 国产精品乱码久久久久久软件| 狠狠人妻久久久久久综合| 国产精品一区二区久久精品无码| …久久精品99久久香蕉国产 | 久久99国产精品二区不卡| 伊人久久大香线蕉av一区| 久久久久亚洲AV无码专区首JN |