WARush

#include<iostream>
using namespace std;
const int V=101;
const int E=101;
#define typec int                      // type of cost
const typec inf=0x3f3f3f3f;            // max of cost
int n, m, pre[V], edge[E][3];
typec dist[V];
int relax (int u, int v, typec c)
{
    if (dist[v] > dist[u] + c)
    {
        dist[v] = dist[u] + c;
        pre[v] = u;
        return 1;
    }
    return 0;
}
int bellman (int src)
{
    int i, j;
    for (i=0; i<n; ++i)
    {
        dist[i] = inf;
        pre[i] = -1;
    }
    dist[src] = 0;
    bool flag;
    for (i=1; i<n; ++i)
    {
        flag = false; 
        for (j=0; j<m; ++j)
        {
            if( 1 == relax(edge[j][0], edge[j][1],
                           edge[j][2])  ) flag = true;
        }
        if( !flag ) break;
    }
    for (j=0; j<m; ++j)
    {
        if (1 == relax(edge[j][0], edge[j][1], edge[j][2]))
            return 0
    }
    return 1;
}

int main()
{
    int i;
    int src;
    cin>>n>>m;

    for(i=0; i<m; ++i)
    {
        cin>>edge[i][0]>>edge[i][1]>>edge[i][2];
        
    }

  
    cin>>src;
    cout<<bellman(src)<<"\n";
    for(i=0; i<n; i++)
    {
        cout<<dist[i]<<' ';
    }
    cout<<'\n';
    return 0;
}

模版的使用，Bellman-Ford算法，复杂度O(VE)，可解决负权边，判别负权回路。

额外采用Yen氏改进，但不降低渐进复杂度。还可采用队列优化成SPFA(Shortest Path Faster Algorithm)。