// LLP-Delta-Stepping: bucket-based relaxation with light/heavy edge phases.
// This algorithm has complex control flow (repeat/until, set comprehensions)
// beyond the standard forbidden/advance pattern.
// The forbidden predicates are:
//   forbidden_L(v): exists (u,v) in E_light : G[u] + w[u][v] < G[v]
//   forbidden_H(v): exists (u,v) in E_heavy : G[u] + w[u][v] < G[v]

class LLPDeltaStepping {
  void LLPDeltaStepping(int[][] pre, int[][] w, boolean[][] isLight, int[] G, int delta) {
    G[s] = 0;
    boolean changed = true;
    while (changed) {
      changed = false;
      int j = 0;
      while (j < G.length) {
        if (relaxLight(j, pre, w, isLight, G, delta)) { changed = true; };
        j = j + 1;
      };
      j = 0;
      while (j < G.length) {
        if (relaxHeavy(j, pre, w, isLight, G, delta)) { changed = true; };
        j = j + 1;
      }
    }
  }

  boolean relaxLight(int v, int[][] pre, int[][] w, boolean[][] isLight, int[] G, int delta) {
    boolean relaxed = false;
    int k = 0;
    while (k < pre[v].length) {
      int u = pre[v][k];
      if (isLight[u][v] && G[u] + w[u][v] < G[v]) {
        G[v] = G[u] + w[u][v];
        relaxed = true;
      };
      k = k + 1;
    };
    return relaxed;
  }

  boolean relaxHeavy(int v, int[][] pre, int[][] w, boolean[][] isLight, int[] G, int delta) {
    boolean relaxed = false;
    int k = 0;
    while (k < pre[v].length) {
      int u = pre[v][k];
      if (!isLight[u][v] && G[u] + w[u][v] < G[v]) {
        G[v] = G[u] + w[u][v];
        relaxed = true;
      };
      k = k + 1;
    };
    return relaxed;
  }
}