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; }
