結果

問題 No.1 道のショートカット
コンテスト
ユーザー vjudge1
提出日時 2025-09-04 21:20:20
言語 TypeScript
(5.7.2)
結果
AC  
実行時間 112 ms / 5,000 ms
コード長 1,661 bytes
コンパイル時間 11,451 ms
コンパイル使用メモリ 264,648 KB
実行使用メモリ 54,380 KB
最終ジャッジ日時 2025-09-04 21:20:37
合計ジャッジ時間 15,666 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

function main(): void {
    const input = require('fs').readFileSync(0, 'utf-8').trim().split(/\s+/);
    let index = 0;
    
    const N = parseInt(input[index++]);
    const C = parseInt(input[index++]);
    const V = parseInt(input[index++]);
    
    const S: number[] = [];
    const T: number[] = [];
    const Y: number[] = [];
    const M: number[] = [];
    
    for (let i = 0; i < V; i++) { S.push(parseInt(input[index++]) - 1); }
    for (let i = 0; i < V; i++) { T.push(parseInt(input[index++]) - 1); }
    for (let i = 0; i < V; i++) { Y.push(parseInt(input[index++])); }
    for (let i = 0; i < V; i++) { M.push(parseInt(input[index++])); }
    
    const graph: Array<Array<[number, number, number]>> = Array.from({length: N}, () => []);
    for (let i = 0; i < V; i++) {
        graph[S[i]].push([T[i], Y[i], M[i]]);
    }
    
    const INF = 1e9;
    const dp: number[][] = Array.from({length: N}, () => 
        Array.from({length: C + 1}, () => INF)
    );
    dp[0][C] = 0;
    
    for (let i = 0; i < N; i++) {
        for (let k = C; k >= 0; k--) {
            if (dp[i][k] === INF) continue;
            
            for (const [to, cost, time] of graph[i]) {
                if (k >= cost) {
                    const newCost = k - cost;
                    const newTime = dp[i][k] + time;
                    if (newTime < dp[to][newCost]) {
                        dp[to][newCost] = newTime;
                    }
                }
            }
        }
    }
    
    const result = Math.min(...dp[N - 1]);
    console.log(result === INF ? -1 : result);
}

// For Node.js environment
if (require.main === module) {
    main();
}
0