学步园

#include<iostream>
using namespace std;
const int oo=1000000;
int n,m;//n为点的个数 m为边的条数
int begin,end;//begin为起始点 end为结束点
struct bian
{
       int a,b;
       int w;
}*E;
int *D;
int Ford()
{
    int i,j;
    for (i=1;i<=m;i++)
    {
        for (j=1;j<=n;j++)
        {//松弛
            if(D[E[i].b]>D[E[i].a]+E[i].w)
            {
                D[E[i].b]=D[E[i].a]+E[i].w;
            }
        }
    }
    return 0;
}
int main(){
    int i,j;
    int a,b,w;
    cin>>n>>m>>begin>>end;
    D=new int [n+1];
    E=new bian[m+1];
    for (i=1;i<=m;i++)
    {
        cin>>a>>b>>w;
        E[i].a=a;
        E[i].b=b;
        E[i].w=w;
    }
    memset(D,oo,sizeof(int)*(n+1));
    D[begin]=0;
    Ford();
    for (i=1;i<=n;i++)
    {
        cout<<D[i]<<' ';
    }
    return 0;
}

BellmanFord算法
  g[][],是一个矩阵图，用于表达有向图 点之间的权重。

inline void init(int d[M],int n,int s){  //初始化图

                int
i;

                for(i=1;i<=n;i++)    d[i]=2000000000;

                d[s]=0;

}

inline void relax(int d[M],int u,int v,int duv){

                if(d[v]>d[u]+duv)   d[v]=d[u]+duv;

}

void bell_man(int g[M][M],int d[M],int n,int s){ //n个结点 s为源点

                int
i,j,k;

                init(d,n,s);

                for(k=1;k<n;k++){

                                for(i=1;i<=n;i++)

                                                for(j=1;j<=n;j++){

                                                                if(g[i][j]!=0)
relax(d,i,j,g[i][j]);

                                                }

                }

}