JulyRina's blog
welcome to July Rina's blog
posts - 22,comments - 1,trackbacks - 0
题目大意:求图上单点到单点之间的最短路。

题目分析:让我们考虑没有负边的情况。在Bellman-Ford算法中,如果dist[i]还不是最短距离的话,那么即使进行dist[j]=dist[i]+(从i到j的边的权值)的更新,dist[j]也不会变成最短距离。而且,即使dist[i]没有变化,每一次循环也要检查一遍从i出发的所有变。这显然是很浪费时间的。因此可以对算法作如下修改。
(1)找到最短距离已经确定的顶点,从他出发更新相邻顶点的最短距离。
(2)此后不再需要关心(1)中的“最短距离已经确定的顶点”。
在(1)和(2)中提到的“最短距离已经确定的”要怎么得到时问题的关键。在最开始时,只有起点的最短距离是确定的。而在尚未使用过的顶点中,距离dist[i]最小的顶点就会加入“最短距离已经确定的顶点”的阵营。这是因为由于不会存在负边,所以dist[i]不会在之后的更新中变小。这个算法叫做Dijkstra算法。
#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;
#define INF (1<<29)
const int maxn = 1010;

typedef pair<intint> P;
vector<P> G[maxn];
int V, E, dist[maxn];
bool vis[maxn];

void dijkstra(int s) {
    fill(dist, dist + V, INF);
    fill(vis, vis + V, false);
    dist[s] = 0;
    while(true) {
        int u = -1;
        for(int i=0;i<V;i++)
            if(!vis[i] && (u == -1 || dist[i] < dist[u]))
                u = i;
        if(u == -1) break;
        vis[u] = true;
        int sz = G[u].size();
        for(int i=0;i<sz;i++) {
            int v = G[u][i].first;
            int w = G[u][i].second;
            dist[v] = min(dist[v], dist[u] + w);
        }
    }
}

int main() {
    scanf("%d%d" , &E, &V);
    for(int i=0;i<V;i++) G[i].clear();
    for(int i=0;i<E;i++) {
        int u, v, w;
        scanf("%d%d%d" , &u, &v, &w);
        u --; v --;
        G[u].push_back(make_pair(v, w));
        G[v].push_back(make_pair(u, w));
    }
    dijkstra(0);
    printf("%d\n", dist[V-1]);
    return 0;
}
posted on 2015-02-13 19:34 JulyRina 阅读(202) 评论(0)  编辑 收藏 引用 所属分类: 解题报告

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理