/* TRITIUM-PROVENANCE sha256=cecf307e190155d45c2cc7a93a750de16f8670bcbb0f247d9967748079f4e335 lang=c */
/* TRITIUM-HEIGHT high=0.16 mid=0.31 low=0.52 fns=11 */
#include <stdint.h>
#include <math.h>

// TRITIUM-PSEUDO fn=dist_init
//| fn dist_init(dist, n, start, inf):
//|   return 0L
// TRITIUM-HEIGHT fn=dist_init high=0.00 mid=0.34 low=0.66
int64_t dist_init(int64_t* dist, int64_t n, int64_t start, int64_t inf) {
    int64_t i;

    i = 0L;
    while (i < n) {
        dist[i] = inf;
        i = (i + 1L);
    }
    dist[start] = 0L;
    return 0L;
}

// TRITIUM-PSEUDO fn=heap_push
//| fn heap_push(heap_dist, heap_node, n, d, u):
//|   return n + 1L
// TRITIUM-HEIGHT fn=heap_push high=0.00 mid=0.33 low=0.67
int64_t heap_push(int64_t* heap_dist, int64_t* heap_node, int64_t n, int64_t d, int64_t u) {
    int64_t i;
    int64_t parent;

    i = n;
    heap_dist[i] = d;
    heap_node[i] = u;
    while (i > 0L) {
        parent = (i - 1L) / 2L;
        if (heap_dist[i] >= heap_dist[parent]) {
            break;
        }
        int64_t swap = heap_dist[i];
        heap_dist[i] = heap_dist[parent];
        heap_dist[parent] = swap;
        int64_t tmp_node = heap_node[i];
        heap_node[i] = heap_node[parent];
        heap_node[parent] = tmp_node;
        i = parent;
    }
    return n + 1L;
}

// TRITIUM-PSEUDO fn=heap_min_d
//| fn heap_min_d(heap_dist, heap_node, n):
//|   return heap_dist[0L]
// TRITIUM-HEIGHT fn=heap_min_d high=0.00 mid=0.00 low=1.00 role=leaf_charset
int64_t heap_min_d(int64_t* heap_dist, int64_t* heap_node, int64_t n) {

    return heap_dist[0L];
}

// TRITIUM-PSEUDO fn=heap_min_u
//| fn heap_min_u(heap_dist, heap_node, n):
//|   return heap_node[0L]
// TRITIUM-HEIGHT fn=heap_min_u high=0.00 mid=0.00 low=1.00 role=leaf_charset
int64_t heap_min_u(int64_t* heap_dist, int64_t* heap_node, int64_t n) {

    return heap_node[0L];
}

// TRITIUM-PSEUDO fn=heap_pop
//| fn heap_pop(heap_dist, heap_node, n):
//|   return n - 1L
// TRITIUM-HEIGHT fn=heap_pop high=0.00 mid=0.42 low=0.58
int64_t heap_pop(int64_t* heap_dist, int64_t* heap_node, int64_t n) {
    int64_t i;
    int64_t diff;
    int64_t sum_2;
    int64_t sum;
    int64_t i_2;

    diff = n - 1L;
    heap_dist[0L] = heap_dist[diff];
    heap_node[0L] = heap_node[diff];
    i = 0L;
    diff = (diff - 1L);
    while (1) {
        sum_2 = (i * 2L) + 1L;
        sum = sum_2 + 1L;
        if (sum_2 > diff) {
            break;
        }
        i_2 = sum_2;
        if (sum <= diff) {
            if (heap_dist[sum] < heap_dist[sum_2]) {
                i_2 = sum;
            }
        }
        if (heap_dist[i] <= heap_dist[i_2]) {
            break;
        }
        int64_t swap = heap_dist[i];
        heap_dist[i] = heap_dist[i_2];
        heap_dist[i_2] = swap;
        int64_t tmp_node = heap_node[i];
        heap_node[i] = heap_node[i_2];
        heap_node[i_2] = tmp_node;
        i = i_2;
    }
    return n - 1L;
}

// TRITIUM-PSEUDO fn=list_get
//| fn list_get(vals, i):
//|   return vals[i]
// TRITIUM-HEIGHT fn=list_get high=0.00 mid=0.00 low=1.00 role=leaf_charset
int64_t list_get(int64_t* vals, int64_t i) {

    return vals[i];
}

// TRITIUM-PSEUDO fn=stale_visit
//| fn stale_visit(dist, u, d):
//|   return (d > (list_get(dist, u))) ? 1L : 0L
// TRITIUM-HEIGHT fn=stale_visit high=0.00 mid=1.00 low=0.00 role=leaf_charset
int64_t stale_visit(int64_t* dist, int64_t u, int64_t d) {

    return (d > (list_get(dist, u))) ? 1L : 0L;
}

// TRITIUM-PSEUDO fn=relax_edge
//| fn relax_edge(dist, heap_dist, heap_node, heap_len, u, v, w):
//|   sum
//|   sum = dist[u] + w
//|   if (sum < dist[v]) {
//|     dist[v] = sum
//|     heap_len = heap_push(heap_dist, heap_node, heap_len, sum, v)
//|   }
//|   return heap_len
// TRITIUM-HEIGHT fn=relax_edge high=0.21 mid=0.38 low=0.41 role=leaf_charset
int64_t relax_edge(int64_t* dist, int64_t* heap_dist, int64_t* heap_node, int64_t heap_len, int64_t u, int64_t v, int64_t w) {
    int64_t sum;

    sum = dist[u] + w;
    if (sum < dist[v]) {
        dist[v] = sum;
        heap_len = heap_push(heap_dist, heap_node, heap_len, sum, v);
    }
    return heap_len;
}

// TRITIUM-PSEUDO fn=edge_relax
//| fn edge_relax(dist, heap_dist, heap_node, heap_len, dest, weight, e, u):
//|   return relax_edge(dist, heap_dist, heap_node, heap_len, u, list_get(dest, e), list_get(weight, e))
// TRITIUM-HEIGHT fn=edge_relax high=0.67 mid=0.33 low=0.00
int64_t edge_relax(int64_t* dist, int64_t* heap_dist, int64_t* heap_node, int64_t heap_len, int64_t* dest, int64_t* weight, int64_t e, int64_t u) {

    return relax_edge(dist, heap_dist, heap_node, heap_len, u, list_get(dest, e), list_get(weight, e));
}

// TRITIUM-PSEUDO fn=scan_neighbors
//| fn scan_neighbors(dist, heap_dist, heap_node, heap_len, dest, weight, offsets, u):
//|   edge_relax(...)
//|   return heap_len
// TRITIUM-HEIGHT fn=scan_neighbors high=0.27 mid=0.40 low=0.33
int64_t scan_neighbors(int64_t* dist, int64_t* heap_dist, int64_t* heap_node, int64_t heap_len, int64_t* dest, int64_t* weight, int64_t* offsets, int64_t u) {
    int64_t idx;

    idx = list_get(offsets, u);
    while (idx < (list_get(offsets, u + 1L))) {
        heap_len = edge_relax(dist, heap_dist, heap_node, heap_len, dest, weight, idx, u);
        idx = (idx + 1L);
    }
    return heap_len;
}

// TRITIUM-PSEUDO fn=dijkstra
//| fn dijkstra(n, offsets, dest, weight, start, dist, heap_dist, heap_node):
//|   dist_init(...)
//|   heap_push(...)
//|   heap_min_u(...)
//|   heap_pop(...)
//|   stale_visit(...)
//|   heap_min_d(...)
//|   scan_neighbors(...)
//|   return 0L
// TRITIUM-HEIGHT fn=dijkstra high=0.65 mid=0.23 low=0.12
int64_t dijkstra(int64_t n, int64_t* offsets, int64_t* dest, int64_t* weight, int64_t start, int64_t* dist, int64_t* heap_dist, int64_t* heap_node) {
    int64_t inf;
    int64_t heap_len;
    int64_t u;

    inf = 1000000000L;
    dist_init(dist, n, start, inf);
    heap_len = heap_push(heap_dist, heap_node, 0L, 0L, start);
    while (heap_len > 0L) {
        u = heap_min_u(heap_dist, heap_node, heap_len);
        heap_len = heap_pop(heap_dist, heap_node, heap_len);
        if (!(((stale_visit(dist, u, heap_min_d(heap_dist, heap_node, heap_len))) == 1L))) {
            heap_len = scan_neighbors(dist, heap_dist, heap_node, heap_len, dest, weight, offsets, u);
        }
    }
    return 0L;
}