[UVa] 341 Non-Stop Travel.cpp

#include <cstdio>
#include <vector>
using namespace std;
#define Inf 99999999
struct Edge{
    int A;
    int B;
    int Time;
}E[100];
int nOfE;
int Dis[12];
int Pre[12];

void Initial(int &NI, int &Start);
void BellmanFord(int &NI);
bool Relax(Edge &E);
void Output(int &Start, int &End);

int main()
{
    int NI, Start, End;
    while (scanf("%d", &NI) && NI) {
        nOfE = 0;
        for (int i = 1, n; i <= NI; ++i) {
            scanf("%d", &n);
            for (int j = 0; j < n; ++j) {
                scanf("%d %d", &E[nOfE].B, &E[nOfE].Time);
                E[nOfE++].A = i;
            }
        }
        scanf("%d %d", &Start, &End);
        Initial(NI, Start);
        BellmanFord(NI);
        Output(Start, End);
    }
}
void Initial(int &NI, int &Start)
{
    for (int i = 1; i <= NI; ++i) {
        Dis[i] = Inf;
        Pre[i] = 0;
    }
    Dis[Start] = 0;
}
void BellmanFord(int &NI)
{
    for (int i = 0; i < NI - 1; ++i) {
        bool change = 0;
        for (int j = 0; j < nOfE; ++j)
            if (Relax(E[j]))
                change = 1;
        if (!change)
            return;
    }
}
bool Relax(Edge &E)
{
    int x = E.A;
    int y = E.B;
    if (Dis[x] + E.Time < Dis[y]){
        Dis[y] = Dis[x] + E.Time;
        Pre[y] = x;
        return true;
    }
    return false;
}
void Output(int &Start, int &End)
{
    static int Case = 1;
    printf("Case %d: Path =", Case++);
    vector<int> Ans;
    int i = End;
    while (i != Start) {
        i = Pre[i];
        Ans.push_back(i);
    }
    for (int i = Ans.size() - 1; i >= 0; --i)
        printf(" %d", Ans[i]);
    printf(" %d; %d second delay\n", End, Dis[End]);
}