Bellman算法

当图有负圈的时候可以用这个判断最短路！

【时间复杂度】O(\(nm\))

&代码：

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int INF = 0x3f3f3f3f;

#define cle(a,val) memset(a,(val),sizeof(a))

#define SI(N) scanf("%d",&(N))

#define SII(N,M) scanf("%d %d",&(N),&(M))

#define SIII(N,M,K) scanf("%d %d %d",&(N),&(M),&(K))

#define rep(i,b) for(int i=0;i<(b);i++)

#define rez(i,a,b) for(int i=(a);i<=(b);i++)

#define red(i,a,b) for(int i=(a);i>=(b);i--)

const ll LINF = 0x3f3f3f3f3f3f3f3f;

#define PU(x) puts(#x);

#define PI(A) cout<<(A)<<endl;

#define DG(x) cout<<#x<<"="<<(x)<<endl;

#define DGG(x,y) cout<<#x<<"="<<(x)<<" "<<#y<<"="<<(y)<<endl;

#define DGGG(x,y,z) cout<<#x<<"="<<(x)<<" "<<#y<<"="<<(y)<<" "<<#z<<"="<<(z)<<endl;

#define PIar(a,n) rep(i,n)cout<<a[i]<<" ";cout<<endl;

#define PIarr(a,n,m) rep(aa,n){rep(bb, m)cout<<a[aa][bb]<<" ";cout<<endl;}

const double EPS = 1e-9 ;

/*  ////////////////////////   C o d i n g  S p a c e   ////////////////////////  */

const int MAXN = 1000 + 9 ;

struct Edge{

    int from,to,dist;

    Edge(int u,int v,int d):from(u),to(v),dist(d){}

};

vector<Edge> edges;

vector<int> G[MAXN];

void Init(int n){

    rep(i,n) G[i].clear();

    edges.clear();

}

void AddEdge(int u,int v,int d){

    edges.push_back(Edge(u,v,d));

    G[u].push_back(edges.size()-1);

}

int n,m;

int inq[MAXN],cnt[MAXN],d[MAXN],p[MAXN];

bool BellmanFord(int s){

    queue<int> Q;

    memset(inq,0,sizeof(inq));

    memset(cnt,0,sizeof(cnt));

    for(int i=0;i<n;i++)

        d[i]=INF;

    d[s]=0;

    inq[s]=true;

    Q.push(s);

    while(!Q.empty()){

        int u=Q.front(); Q.pop();

        inq[u]=false;

        for (int i=0;i<G[u].size();i++){

            Edge& e=edges[G[u][i]];

            if (d[u]<INF&&d[e.to]>d[u]+e.dist){

                d[e.to]=d[u]+e.dist;

                p[e.to]=G[u][i];

                if (!inq[e.to]){

                    Q.push(e.to);

                    inq[e.to]=true;

                    if (++cnt[e.to]>n) return false;

                }

            }

        }

    }

}

void Solve()

{

    while(cin>>n>>m){

        int a,b,c;

        Init(n);

        for(int i=0;i<n;i++){

            scanf("%d%d%d",&a,&b,&c);

            //the number input is started from 1,but the code is started from 0. so must -1

            a--,b--;

            AddEdge(a,b,c);

        }

        BellmanFord(0);

        PIar(d,n)

    }

}

int main()

{

#ifndef ONLINE_JUDGE

    freopen("1.in", "r", stdin);

    freopen("1.out","w",stdout);

#endif

//iostream::sync_with_stdio(false);

//cin.tie(0), cout.tie(0);

    // int T;cin>>T;while(T--)

    Solve();

    return 0;

}

测试：

输入

5 5

1 2 1

1 3 7

2 5 4

3 4 3

3 5 2

输出

0 1 7 10 5