[POJ] 2387 Til the Cows Come Home.cpp

#include <cstdio>
using namespace std;
#define Inf 99999999

struct Edge{
    int x;
    int y;
    int Len;
}E[2001];
int Dis[1001];

void Initial(const int &N);
void BellmanFord(const int &N, const int &T);
bool Relax(const Edge &E);

int main()
{
    int T, N;
    while (scanf("%d %d", &T, &N) != EOF)
    {
        Initial(N);
        for (int i = 0; i < T; ++i)
            scanf("%d %d %d", &E[i].x, &E[i].y, &E[i].Len);

        BellmanFord(N, T);

        printf("%d\n", Dis[1]);
    }
}
void Initial(const int &N)
{
    Dis[N] = 0;
    for (int i = 1; i < N; ++i)
        Dis[i] = Inf;
}
void BellmanFord(const int &N, const int &T)
{
    for (int times = 0; times < N - 1; ++times){
        bool NotOK = 0;
        for (int i = 0; i < T; ++i)
            if (Relax(E[i])) NotOK = 1;
        if (!NotOK) return;
    }
}
bool Relax(const Edge &E)
{
    bool change = 0;
    if (Dis[E.x] + E.Len < Dis[E.y]){
        Dis[E.y] = Dis[E.x] + E.Len;
        change = 1;
    }
    if (Dis[E.y] + E.Len < Dis[E.x]){
        Dis[E.x] = Dis[E.y] + E.Len;
        change = 1;
    }
    return change;
}