// An implementation of
// https://sampleprograms.io/projects/dijkstra/

val shortestPath = { !sys.aryi64 matrix, int nodes, int src, int dst ->
    i64 infinity = (1 << 63)-1;
    var dist = new i64[nodes];
    var visited = new sys.adt.bitset();
    // All nodes are infinitely far from each other
    for( int i=0; i<nodes; i++ ) dist[i] = infinity;
    // Starting point is zero far from starting point
    dist[src] = 0;

    i64 result = -1;
    int count = 0;
    while( count < nodes && result < 0 ) {
        int nearest = -1;
        i64 best = infinity;
        for( int node=0; node<nodes; node++ )
            if( !visited.get(node) && dist[node] < best ) {
                nearest = node;
                best = dist[node];
            }
        if( nearest < 0 ) count = nodes;
        else {
            if( nearest == dst ) return best;
            visited.set(nearest);
            for( int node=0; node<nodes; node++ ) {
                i64 weight = matrix.get(nearest*nodes + node);
                if( weight > 0 && !visited.get(node) && best+weight < dist[node] )
                    dist[node] = best+weight;
            }
        }
        count++;
    }
    return result;
};

val usage = { ->
    sys.io.p("Usage: please provide three inputs: a serialized matrix, a source node and a destination node\n");
    return 0;
};

val main = { u8[~][] args ->
    // Exactly 3 args
    if( args# != 4 ) return usage();
    // First is a serialized square matrix of positive numbers
    var matrix = sys.aryi64.parseAryI64(args[1]);
    if( !matrix ) return usage();
    if( !matrix.len ) return usage();
    // All numbers are positive
    for( int i=0; i<matrix.len; i++ )
        if( matrix.get(i) < 0 ) return usage();
    // Matrix is square
    int nodes = 0;
    while( nodes*nodes < matrix.len ) nodes++;
    if( nodes*nodes != matrix.len )
        return usage();         // Not a square matrix

    // src,dst are values within the matrix
    i64 src = sys.aryu8.atoi(args[2]);
    i64 dst = sys.aryu8.atoi(args[3]);
    if( src < 0 || src >= nodes || dst < 0 || dst >= nodes )
        return usage();         // Source and destination land within the graph

     i64 cost = shortestPath(matrix,nodes,src,dst);
     if( cost >= 0 ) {
         new sys.aryu8().num(cost).add('\n').write(1);
         return 0;
     }
    return usage();
};