結果
問題 |
No.1 道のショートカット
|
ユーザー |
![]() |
提出日時 | 2022-02-01 18:33:14 |
言語 | TypeScript (5.7.2) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,315 bytes |
コンパイル時間 | 8,904 ms |
コンパイル使用メモリ | 230,424 KB |
実行使用メモリ | 45,440 KB |
最終ジャッジ日時 | 2024-12-31 16:44:26 |
合計ジャッジ時間 | 13,405 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 38 WA * 2 |
ソースコード
function main(line) { const n = Number(line.shift()); const c = Number(line.shift()); const v = Number(line.shift()); const s = line.shift().split(" ").map(x=>Number(x)-1); const t = line.shift().split(" ").map(x=>Number(x)-1); const y = line.shift().split(" ").map(x=>Number(x)); const m = line.shift().split(" ").map(x=>Number(x)); const arr = []; for(let i=0; i<v; i++) { arr.push({s:s[i], t:t[i], y:y[i], m:m[i]}); } const dp = []; for(let i=0; i<n; i++) { dp[i] = new Array(n).fill(Number.MAX_SAFE_INTEGER); } const q = [{id:0, money:c, cost:0}]; let minCost = Number.MAX_SAFE_INTEGER; while(q.length > 0) { const now = q.shift(); const id = now.id; const money = now.money; const cost = now.cost; if(id === n-1) { if(cost < minCost) { minCost = cost; } } arr.filter(cur => cur.s === id).forEach(cur => { const nextMoney = money - cur.y; if(nextMoney >= 0) { const nextCost = cost + cur.m; if(dp[cur.s][cur.t] > nextCost) { q.push({id:cur.t, money:nextMoney, cost:nextCost}); dp[cur.s][cur.t] = nextCost; } } }); } console.log(minCost === Number.MAX_SAFE_INTEGER ? -1 : minCost); } main(require("fs").readFileSync("/dev/stdin", "utf8").split("\n"));