結果

問題 No.1 道のショートカット
ユーザー vjudge1
提出日時 2025-06-05 19:22:30
言語 TypeScript
(5.7.2)
結果
AC  
実行時間 102 ms / 5,000 ms
コード長 3,505 bytes
コンパイル時間 7,039 ms
コンパイル使用メモリ 267,748 KB
実行使用メモリ 57,432 KB
最終ジャッジ日時 2025-06-05 19:22:46
合計ジャッジ時間 12,621 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

import { createInterface } from 'node:readline';
import { stdin as input, stdout as output } from 'node:process';

interface Edge {
    to: number;
    cost: number;
    time: number;
}

interface State {
    node: number;
    usedCost: number;
    totalTime: number;
}

class PriorityQueue {
    private heap: State[] = [];

    push(state: State): void {
        this.heap.push(state);
        let i = this.heap.length - 1;
        while (i > 0) {
            const parent = Math.floor((i - 1) / 2);
            if (this.heap[parent].totalTime <= this.heap[i].totalTime) break;
            [this.heap[parent], this.heap[i]] = [this.heap[i], this.heap[parent]];
            i = parent;
        }
    }

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

    get length(): number {
        return this.heap.length;
    }
}

function shortestPath(n: number, c: number, graph: Edge[][]): number {
    const dp: number[][] = Array.from({ length: n }, () => 
        Array(c + 1).fill(Number.MAX_SAFE_INTEGER)
    );
    const pq = new PriorityQueue();

    dp[0][0] = 0;
    pq.push({ node: 0, usedCost: 0, totalTime: 0 });

    while (pq.length > 0) {
        const curr = pq.pop()!;
        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;
                pq.push({ node: edge.to, usedCost: newCost, totalTime: newTime });
            }
        }
    }

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

async function main() {
    const rl = createInterface({ input, output });
    const lines: string[] = [];
    
    for await (const line of rl) {
        lines.push(line);
    }

    const tokens = lines.join(' ').trim().split(/\s+/);
    let ptr = 0;

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

    const graph: Edge[][] = Array.from({ length: n }, () => []);
    const s = tokens.slice(ptr, ptr + v).map(Number);
    ptr += v;
    const t = tokens.slice(ptr, ptr + v).map(Number);
    ptr += v;
    const y = tokens.slice(ptr, ptr + v).map(Number);
    ptr += v;
    const m = tokens.slice(ptr, ptr + v).map(Number);

    for (let i = 0; i < v; i++) {
        graph[s[i] - 1].push({ to: t[i] - 1, cost: y[i], time: m[i] });
    }

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

main().catch(console.error);
0