图论_最短路_bellman.cpp

一些ACM基本算法的测试源码

#include<iostream>
using namespace std;

const int SIZE = 505;
const int INF = 1000000000;


struct Edge{
    int s, t, w;       
}edge[SIZE];

int n, e;
int dist[SIZE];

bool bellman()
{
    int i, j;
    for(i = 0; i < n; i ++)
        dist[i] = INF;
    dist[0] = 0;
    for(i = 1; i < n; i ++)
        for(j = 0; j < e; j ++)
            if(dist[edge[j].t] > dist[edge[j].s] + edge[j].w)
                dist[edge[j].t] = dist[edge[j].s] + edge[j].w;
    for(i = 0; i < e; i ++)
        if(dist[edge[i].t] > dist[edge[i].s] + edge[i].w)  return false;
    return true;         
}

int main()
{
    scanf("%d%d", &n, &e);
    for(int i = 0; i < e; i ++)
        scanf("%d%d%d", &edge[i].s, &edge[i].t, &edge[i].w);//这里处理的是有向图    
    if(bellman())
    {
        for(int i = 0; i < n; i ++)
            printf("%d\n", dist[i]);
    }
    else  printf("存在负环!\n");
    system("pause");
    return 0;   
}