Cod sursă (job #133120)

// Algoritm: zborul optim va obține dragoni tot mai mari,
// până obține unul cu care poate ajunge la N. Sortăm deci dragonii
// și facem un șir de Dijkstra-uri cu dragoni tot mai mari. Cu fiecare dragon
// obținut, facem un Dijkstra optimizând distanțele totale.
#include <algorithm>
#include <stdio.h>

#define MAX_N 800
#define MAX_M 6000
#define NIL -1
#define INFTY 1000000000

typedef struct {
  int v, d, next;
} cell;

int range[MAX_N];    // distanța maximă a fiecărui dragon
cell l[2 * MAX_M];   // liste de adiacență alocate static
int adj[MAX_N];      // capetele listelor
int d[MAX_N];        // distanțele minime (Dijkstra)
int global[MAX_N];   // distanțele minime prin mai multe Dijkstra
int h[MAX_N];        // min-heap după d
int hpos[MAX_N];     // pointeri în heap
int rpos[MAX_N];     // dragonii sortați după range
int n, m;

void addEdge(int u, int v, int d, int pos) {
  l[pos].v = v;
  l[pos].d = d;
  l[pos].next = adj[u];
  adj[u] = pos;
}

int heapExtract(int *size) {
  int result = h[0];
  hpos[h[0]] = NIL;
  (*size)--;
  h[0] = h[*size];
  hpos[h[*size]] = 0;

  // sift-down
  int k = 0, best, changed;
  do {
    changed = 0;
    best = k;
    if ((2 * k + 1 < *size) && (d[h[2 * k + 1]] < d[h[best]])) {
      best = 2 * k + 1;
    }
    if ((2 * k + 2 < *size) && (d[h[2 * k + 2]] < d[h[best]])) {
      best = 2 * k + 2;
    }
    if (best != k) {
      hpos[h[k]] = best;
      hpos[h[best]] = k;
      int tmp = h[k];
      h[k] = h[best];
      h[best] = tmp;
      k = best;
      changed = 1;
    }
  } while (changed);
  return result;
}

void heapSiftUp(int v) {
  int k = hpos[v];
  int p = (k - 1) / 2;
  while (k && (d[h[k]] < d[h[p]])) {
    hpos[h[k]] = p;
    hpos[h[p]] = k;
    int tmp = h[k];
    h[k] = h[p];
    h[p] = tmp;
    k = p;
    p = (k - 1) / 2;
  }
}

void dijkstra(int start) {
  // Inițializăm distanțele și heapul. Pune fiecare nod i pe poziția i
  // în heap, apoi schimbă nodurile start și 0.
  for (int i = 0; i < n; i++) {
    d[i] = INFTY;
    h[i] = i;
    hpos[i] = i;
  }
  d[start] = 0;
  h[0] = start;
  hpos[start] = 0;
  h[start] = 0;
  hpos[0] = start;

  int hsize = n;
  while (hsize && (d[h[0]] < INFTY)) {
    int u = heapExtract(&hsize);
    for (int p = adj[u]; p != NIL; p = l[p].next) {
      if ((l[p].d <= range[start]) && (d[u] + l[p].d < d[l[p].v])) {
        d[l[p].v] = d[u] + l[p].d;
        heapSiftUp(l[p].v);
      }
    }
  }
}

int cmp(int a, int b) {
  return range[a] < range[b];
}

int main(void) {
  int task, u, v, dist;

  FILE *f = fopen("dragoni2.in", "r");
  fscanf(f, "%d%d%d", &task, &n, &m);
  for (int i = 0; i < n; i++) {
    fscanf(f, "%d", &range[i]);
    adj[i] = NIL;
  }
  for (int i = 0; i < m; i++) {
    fscanf(f, "%d%d%d", &u, &v, &dist);
    addEdge(u - 1, v - 1, dist, 2 * i);
    addEdge(v - 1, u - 1, dist, 2 * i + 1);
  }
  fclose(f);

  int answer = 0;
  if (task == 1) {
    dijkstra(0);
    for (int i = 0; i < n; i++) {
      if ((d[i] < INFTY) && (range[i] > answer)) {
        answer = range[i];
      }
    }
  } else {
    // Sortăm dragonii crescător după Dmax
    for (int i = 0; i < n; i++) {
      rpos[i] = i;
    }
    std::sort(rpos, rpos + n, cmp); // pardon

    global[0] = 0;
    for (int i = 1; i < n; i++) {
      global[i] = INFTY;
    }
    // Examinăm dragonul 0 și pe cei mai buni
    for (int i = 0; i < n; i++) {
      if (range[rpos[i]] >= range[0]) {
        // Facem un Dijkstra pornind din insula dragonului
        // și vedem dacă, cu acest nou dragon, putem optimiza distanțele
        u = rpos[i];
        int baseCost = global[u];
        dijkstra(u);
        for (int i = 0; i < n; i++) {
          if (baseCost + d[i] < global[i]) {
            global[i] = baseCost + d[i];
          }
        }
      }
    }
    answer = global[n - 1];
  }

  f = fopen("dragoni2.out", "w");
  fprintf(f, "%d\n", answer);
  fclose(f);
}