Mastot

const readline = require('readline');
const r = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
    terminal: false,
});

let data = '';
r.on('line', input => {
    data += input.toString() + '\n';

    const parsed = data.split('\n');
    const count = 3;
    parsed.pop();

    if (parsed.length >= count) {
        const goal = parseInt(parsed.shift());
        const transmitters = parsed.shift().split(' ').map(a => parseInt(a));
        const costs = parsed.shift().split(' ').map(a => parseInt(a));
        calculate(goal, transmitters, costs);

        r.close();
    }
});

class FibonacciHeap {
    constructor() {
        this.keys = new Set();
        this.values = [];
    }

    add(key, priority) {
        key = parseInt(key);
        priority = parseInt(priority);

        if(!this.keys.has(key)) {
            this.keys.add(key);
            this.values.push([key, priority]);
        } else {
            this.values.map(a => {
                if(a[0] === key) {
                    a[1] = priority;
                }

                return a;
            });
        }

        this.values.sort((a, b) => a[1] - b[1]);
    }

    get(key) {
        return this.values.find(a => a[0] === key);
    }

    has(id) {
        return this.keys.has(id);
    }

    shift() {
        if(this.getLength() === 0) return null;

        const a = this.values.shift();
        this.keys.delete(a[0]);

        return a;
    }
    
    getLength() {
        return this.values.length;
    }
}

function dijkstra(graph, from, to) {
    if (from === to) return 1;

    const [heap, explored] = [new FibonacciHeap(), new Set()];
    heap.add(from, 0);

    let node;
    while(node = heap.shift()) {
        const [id, totalCost] = node;
        // console.log(`@ ${id} with cost ${totalCost} (we want ${to})`);
        if (id === to) {
            return totalCost;
        }

        explored.add(id);
        const neighbours = graph[id];
        for(let neighbourId in neighbours) {
            neighbourId = parseInt(neighbourId);
            // console.log(`exploring neighbour ${neighbourId}, current total cost ${totalCost}, cost ${neighbours[neighbourId]}, predicted cost ${neighbours[neighbourId] + totalCost}`);
            if(explored.has(neighbourId)) continue;

            const neighbourCost = neighbours[neighbourId];
            const newCost = neighbourCost + totalCost;
            if(!heap.has(neighbourId)) {
                heap.add(neighbourId, newCost);
            } else {
                if(newCost < heap.get(neighbourId)[1]) {
                    heap.add(neighbourId, newCost);
                }
            }
        }
    }
}

function calculate(goal, transmitters, costs) {
    costs = [1, ...costs];

    const graph = {};
    for(let index in transmitters) {
        index = parseInt(index);

        const [distance, cost] = [transmitters[index], costs[index]];
        const nearbyNodes = {};
        for(let i = index + 1; i < index + distance + 1; i++) {
            nearbyNodes[i] = cost;
        }

        graph[index] = nearbyNodes;
    }

    const cost = dijkstra(graph, 0, goal);
    console.log(cost - 1);
}

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

Test 2

Group: 1, 2, 3

Verdict: ACCEPTED

Test 3

Group: 1, 2, 3

Verdict: ACCEPTED

Test 4

Group: 1, 2, 3

Verdict: ACCEPTED

Test 5

Group: 1, 2, 3

Verdict: ACCEPTED

Test 6

Group: 1, 2, 3

Verdict: ACCEPTED

Test 7

Group: 1, 2, 3

Verdict: ACCEPTED

Test 8

Group: 1, 2, 3

Verdict: ACCEPTED

Test 9

Group: 1, 2, 3

Verdict: ACCEPTED

Test 10

Group: 1, 2, 3

Verdict: ACCEPTED

Test 11

Group: 1, 2, 3

Verdict: ACCEPTED

Test 12

Group: 1, 2, 3

Verdict: ACCEPTED

Test 13

Group: 1, 2, 3

Verdict: ACCEPTED

Test 14

Group: 1, 2, 3

Verdict: ACCEPTED

Test 15

Group: 1, 2, 3

Verdict: ACCEPTED

Test 16

Group: 1, 2, 3

Verdict: ACCEPTED

Test 17

Group: 1, 2, 3

Verdict: ACCEPTED

Test 18

Group: 1, 2, 3

Verdict: ACCEPTED

Test 19

Group: 1, 2, 3

Verdict: ACCEPTED

Test 20

Group: 1, 2, 3

Verdict: ACCEPTED

Test 21

Group: 2, 3

Verdict: ACCEPTED

Test 22

Group: 2, 3

Verdict: TIME LIMIT EXCEEDED

Test 23

Group: 2, 3

Verdict: TIME LIMIT EXCEEDED

Test 24

Group: 2, 3

Verdict: TIME LIMIT EXCEEDED

Test 25

Group: 2, 3

Verdict: TIME LIMIT EXCEEDED

Test 26

Group: 2, 3

Verdict: ACCEPTED

Test 27

Group: 2, 3

Verdict: ACCEPTED

Test 28

Group: 2, 3

Verdict: TIME LIMIT EXCEEDED

Test 29

Group: 2, 3

Verdict: TIME LIMIT EXCEEDED

Test 30

Group: 2, 3

Verdict: TIME LIMIT EXCEEDED

Test 31

Group: 2, 3

Verdict: TIME LIMIT EXCEEDED

Test 32

Group: 2, 3

Verdict: TIME LIMIT EXCEEDED

Test 33

Group: 2, 3

Verdict: TIME LIMIT EXCEEDED

Test 34

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 35

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 36

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 37

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 38

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 39

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 40

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 41

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 42

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 43

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 44

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 45

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 46

Group: 3

Verdict: TIME LIMIT EXCEEDED