• <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>
            JulyRina's blog
            welcome to July Rina's blog
            posts - 22,comments - 1,trackbacks - 0
            題目大意:求圖上單點到單點之間的最短路。
            題目分析:之前我們在同一道問題上分析過了單源最短路問題的Dijkstra算法
            使用鄰接矩陣實現的Dijkstra算法的時間復雜度是O(|V|^2)。使用鄰接表的話,更新最短距離只需要更新每一條邊即可,因此這部分的時間復雜度是O(|E|)。但是每次要枚舉所有的頂點來查找下一個使用的頂點,因此最終復雜度還是O(|V|^2)。在|E|比較小時,大部分經歷放在了查找下一次要是用的頂點上,因此需要使用合適的數據結構對其進行優化。
            需要優化的是數值的插入(更新)和取出最小值兩個操作,因此使用堆就可以了。把每個頂點當前的最短距離用堆維護,在更新最短距離時,把對應的元素往根的方向移動以滿足堆的性質。而每次從堆中取出的最小值就是下一次要使用的頂點。這樣堆中元素共有O(|V|)個,更新和取出數值的操作有O(|E|)次,因此整個算法的復雜度是O(|E|log(V))
            #include <cstdio>
            #include <iostream>
            #include <queue>
            #include <vector>
            using namespace std;
            #define INF (1<<29)
            const int maxn = 1010;

            typedef pair<intint> P; //first是最短距離,second是頂點的編號
            int V, dist[maxn];
            vector<P> G[maxn];

            void dijkstra(int s) {
                //通過指定greater<P>參數,堆按照first從小到大的順序取出值
                priority_queue<P, vector<P>, greater<P> > que;
                fill(dist, dist + V , INF);
                dist[s] = 0;
                while(!que.empty()) que.pop();
                que.push(P(0, s));
                while(!que.empty()) {
                    P p = que.top(); que.pop();
                    int u = p.second;
                    if(dist[u] < p.first) continue;
                    int sz = G[u].size();
                    for(int i=0;i<sz;i++) {
                        int to = G[u][i].second;
                        int cost = G[u][i].first;
                        if(dist[to] > dist[u] + cost) {
                            dist[to] = dist[u] + cost;
                            que.push(P(dist[to], to));
                        }
                    }
                }
            }

            int main() {
                int m;
                scanf("%d%d" , &m, &V);
                for(int i=0;i<V;i++) G[i].clear();
                for(int i=0;i<m;i++) {
                    int from, to, cost;
                    scanf("%d%d%d" , &from, &to, &cost);
                    from --; to --;
                    G[from].push_back(P(cost, to));
                    G[to].push_back(P(cost, from));
                }
                dijkstra(0);
                printf("%d\n", dist[V-1]);
                return 0;
            }
            posted on 2015-02-13 19:38 JulyRina 閱讀(331) 評論(0)  編輯 收藏 引用 所屬分類: 解題報告
            中文字幕无码av激情不卡久久 | 久久99这里只有精品国产| 久久精品国产只有精品2020| 狠狠干狠狠久久| 久久精品国产72国产精福利| 久久天天躁狠狠躁夜夜躁2014| 亚洲精品美女久久777777| 91精品久久久久久无码| 久久久无码精品亚洲日韩蜜臀浪潮| 丁香五月网久久综合| 免费一级欧美大片久久网| 久久久久亚洲AV无码网站| 久久久久久久综合日本| 国内精品久久九九国产精品| 热久久视久久精品18| 欧美久久精品一级c片片| 亚洲国产精品无码久久一线| 久久久久亚洲AV成人网| 91精品国产高清久久久久久io| 亚洲精品无码专区久久同性男| 久久国产精品久久国产精品| 亚洲综合日韩久久成人AV| 武侠古典久久婷婷狼人伊人| 色综合久久精品中文字幕首页| 久久久亚洲欧洲日产国码二区| 亚洲国产日韩综合久久精品| 国产精品欧美久久久久天天影视| 久久99精品久久久久久动态图 | 亚洲国产另类久久久精品| 久久大香萑太香蕉av| 亚洲精品午夜国产va久久| 久久久久国产一区二区| 久久se这里只有精品| 久久久精品人妻无码专区不卡| 国产精品久久久久一区二区三区| 久久亚洲精精品中文字幕| 无码AV波多野结衣久久| 久久亚洲AV成人出白浆无码国产| 无码AV波多野结衣久久| 欧美喷潮久久久XXXXx| 久久丫精品国产亚洲av不卡 |