题目大意：求图上单点到单点之间的最短路。
题目分析：让我们考虑没有负边的情况。在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<
int,
int> 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 阅读(275)
评论(0) 编辑 收藏 引用 所属分类:
解题报告