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 阅读(250) 评论(0)  编辑 收藏 引用 所属分类: 解题报告

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理