Cod sursă (job #294512)

// 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);
}