#include <stdio.h>

#include <stdlib.h>


enum nodes {A=0, B, C, D, E, F, G, H, I, end}; // first and last elements are implicitly the start and end nodes

//                                  A     B     C     D     E     F     G    H     I,    end

int duration [] = {                13,    6,    6,    6,   10  , 20,    8,   12,   5,      0};
int link[]      = {1<<B | 1<<E | 1<<G, 1<<C, 1<<D, 1<<I, 1<<F, 1<<I, 1<<H, 1<<I,   1<<end, 0};
int backlink[]  = {                 0,    0,    0,    0,    0,    0,    0,    0,   0,      0};
int ES[]        = {                 0,    0,    0,    0,    0,    0,    0,    0,   0,      0};
int EF[]        = {                 0,    0,    0,    0,    0,    0,    0,    0,   0,      0};
int LS[]        = {                 0,    0,    0,    0,    0,    0,    0,    0,   0,      0};
int LF[]        = {              9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999,9999,   9999}; // infinite


void WalkForward(int this_node) {
  int next_node;
  for (next_node = 1; next_node < 27; next_node++) {
    if (link[this_node] & (1<<next_node)) { // there exists a path from this_node to next_node;

        backlink[next_node] |= 1<<this_node; // remember the path back

        EF[this_node] = ES[this_node] + duration[this_node];
        if (EF[this_node] > ES[next_node]) ES[next_node] = EF[this_node]; // take the high road

        WalkForward(next_node);
     }
  }
}

void WalkBackward(int this_node) {
  int prev_node;
  if (this_node < 0) return;
  LS[this_node] = LF[this_node] - duration[this_node];
  for (prev_node = 26; prev_node >= 0; prev_node--) { // we already noted the back links

    if (backlink[this_node] & (1<<prev_node)) {
        if (LS[this_node] < LF[prev_node]) LF[prev_node] = LS[this_node]; // take the low road

        WalkBackward(prev_node);
     }
  }
}

void CriticalPath(int this_node) {
  int prev_node;
  if (this_node < 0) return;
  for (prev_node = 26; prev_node >= 0; prev_node--) {
    if ((backlink[this_node] & (1<<prev_node)) && (LS[prev_node]-ES[prev_node] <= 0)) {
        CriticalPath(prev_node); putchar(prev_node+'A');
    }
  }
}

void AllPaths(int this_node, int path, int total_duration)
{
  int node, next_node, ef, branches = 0;
  for (next_node = 1; next_node < 27; next_node++) {
    if (link[this_node] & (1<<next_node)) { // there exists a path from this_node to next_node;

      branches++; AllPaths(next_node, path | (1<<this_node), total_duration+duration[this_node]);
    }
  }
  if (branches == 0) {
    for (node = 0; node < 27; node++) if (path & (1<<node)) putchar(node+'A');
    printf(": %d\n", total_duration);
  }
}

int main(int argc, char **argv) {
    int node = 0;

    WalkForward(A);
    LF[I] = EF[I]; // Anti-symmetric

    WalkBackward(I);

    do {
      printf("   %c(%2d): [ES: %2d  EF: %2d / LS: %2d  LF: %2d] total float = %2d\n",
             node+'A', duration[node], ES[node], EF[node], LS[node], LF[node], LS[node]-ES[node]);
    } while (link[++node] != 0);

    printf("\nAll paths:\n"); AllPaths(A, 0, 0);
    
    printf("\nCritical path: "); CriticalPath(node); putchar('\n');
    
    exit(0); return(1);
}