单源最短路问题

Bellman-ford算法

用edge储存每条路径，d【N】数组表示到源点的最短路长度，将源点的d设置为0，其他的d都设为inf，这样n次操作中每次就只有和源点有关系的d会更新，值得一提的是，这个算法很容易记录路径

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
int n,m;
int cnt;
int pre[10005],d[10005];
struct edge{int u,v,c;
}e[10005];void bell(){for(int k=1; k<=n; ++k)for(int i=0; i<cnt; ++i){int x=e[i].u,y=e[i].v;if(d[x]>d[y]+e[i].c){d[x]=d[y]+e[i].c;pre[x]=y;//记录路径}}
}   int main()
{cnt=0;cin>>n>>m;while(m--){int a,b,cost;cin>>a>>b>>cost;e[cnt].u=a;e[cnt].v=b;e[cnt++].c=cost;e[cnt].u=b;e[cnt].v=a;e[cnt++].c=cost;}bell();return 0;
}