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

题目分析:单源最短路问题是固定一个起点,求它到其他所有点的最短路的问题。终点也固定问题叫做两点之间最短路问题。但是因为单源最短路问题的复杂度是一样的,因此通常当作单源最短路问题来求解。
记从起点s出发到顶点i的最短距离为dist[i]。则下述等式成立。
dist[i] = min{dist[j]+(从j到i的边的权值)|e=(j,i)∈E}
如果给定的图是一个DAG,就可以按托不许给顶点编号,并利用这条递推关系计算出dist。但是,如果图中有圈,就无法利用这样的关系进行计算。
在这种情况下,记当前到顶点i的最短距离为dist[i],并设初值dist[s]=0,dist[i]=INF(足够大的常数),再不断使用这条地推关系式更新dist值,就可以算出新的dist。
只要途中不存在负圈,这样的更新操作就是有限的。结束之后的最短操作就是所求的最短距离了。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;
#define INF (1<<29)
const int maxn = 1010, maxm = 4040;

int n, m;

struct Edge { int from, to, cost; } edge[maxm];
int V, E, dist[maxn];

void bellman_ford(int s) {
    for(int i=0;i<V;i++) dist[i] = INF;
    dist[s] = 0;
    while(true) {
        bool update = fals