結果

問題 No.1 道のショートカット
ユーザー vjudge1
提出日時 2025-06-05 19:01:47
言語 TypeScript
(5.7.2)
結果
AC  
実行時間 103 ms / 5,000 ms
コード長 3,441 bytes
コンパイル時間 11,525 ms
コンパイル使用メモリ 267,072 KB
実行使用メモリ 55,808 KB
最終ジャッジ日時 2025-06-05 19:02:04
合計ジャッジ時間 16,490 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

type Edge = {
    to: number;
    cost: number;
    time: number;
};

type State = {
    node: number;
    usedCost: number;
    totalTime: number;
};

function shortestPath(n: number, c: number, graph: Edge[][]): number {
    // DP table: min time to reach each node with a cost
    const dp: number[][] = Array.from({ length: n }, () => 
        Array(c + 1).fill(Number.MAX_SAFE_INTEGER)
    );
    const pq: State[] = [];

    // Priority queue implementation (min-heap based on totalTime)
    const heapPush = (state: State) => {
        pq.push(state);
        let i = pq.length - 1;
        while (i > 0) {
            const parent = Math.floor((i - 1) / 2);
            if (pq[parent].totalTime <= pq[i].totalTime) break;
            [pq[parent], pq[i]] = [pq[i], pq[parent]];
            i = parent;
        }
    };

    const heapPop = (): State => {
        const min = pq[0];
        const last = pq.pop()!;
        if (pq.length > 0) {
            pq[0] = last;
            let i = 0;
            while (true) {
                const left = 2 * i + 1;
                const right = 2 * i + 2;
                let smallest = i;
                if (left < pq.length && pq[left].totalTime < pq[smallest].totalTime) {
                    smallest = left;
                }
                if (right < pq.length && pq[right].totalTime < pq[smallest].totalTime) {
                    smallest = right;
                }
                if (smallest === i) break;
                [pq[i], pq[smallest]] = [pq[smallest], pq[i]];
                i = smallest;
            }
        }
        return min;
    };

    dp[0][0] = 0;
    heapPush({ node: 0, usedCost: 0, totalTime: 0 });

    while (pq.length > 0) {
        const curr = heapPop();

        if (curr.totalTime > dp[curr.node][curr.usedCost]) continue;

        for (const edge of graph[curr.node]) {
            const newCost = curr.usedCost + edge.cost;
            const newTime = curr.totalTime + edge.time;

            if (newCost <= c && newTime < dp[edge.to][newCost]) {
                dp[edge.to][newCost] = newTime;
                heapPush({ node: edge.to, usedCost: newCost, totalTime: newTime });
            }
        }
    }

    const ans = Math.min(...dp[n - 1]);
    return ans === Number.MAX_SAFE_INTEGER ? -1 : ans;
}

function main() {
    // Read all input from stdin at once
    const input = require('fs').readFileSync(0, 'utf-8').trim().split(/\s+/);
    let ptr = 0;

    const n = parseInt(input[ptr++]);
    const c = parseInt(input[ptr++]);
    const v = parseInt(input[ptr++]);

    const graph: Edge[][] = Array.from({ length: n }, () => []);
    const s: number[] = [];
    const t: number[] = [];
    const y: number[] = [];
    const m: number[] = [];

    // Read s array
    for (let i = 0; i < v; i++) {
        s.push(parseInt(input[ptr++]));
    }
    // Read t array
    for (let i = 0; i < v; i++) {
        t.push(parseInt(input[ptr++]));
    }
    // Read y array
    for (let i = 0; i < v; i++) {
        y.push(parseInt(input[ptr++]));
    }
    // Read m array
    for (let i = 0; i < v; i++) {
        m.push(parseInt(input[ptr++]));
    }

    // Build graph
    for (let i = 0; i < v; i++) {
        const from = s[i] - 1;  // Convert to zero-based indexing
        const to = t[i] - 1;
        graph[from].push({ to, cost: y[i], time: m[i] });
    }

    console.log(shortestPath(n, c, graph));
}

// Run the program
main();
0