Closed upupming closed 3 years ago
Example usage for LeetCode 1928
const n = passingFees.length const m = edges.length const adjList = new AdjList(n, m) // dp[city][time] = fee const dp: number[][] = [...Array(n)].map(() => Array(maxTime + 1).fill(1e9)) for (const e of edges) { adjList.add(e[0], e[1], e[2]) adjList.add(e[1], e[0], e[2]) } const q = new Queue<number[]>() dp[0][0] = passingFees[0] q.push([0, 0]) while (q.size()) { const [city, time] = q.shift()! for (const e of adjList.edges(city)) { const [nextCity, edge] = e const nextTime = time + edge if (nextTime > maxTime) continue if (dp[nextCity][nextTime] > dp[city][time] + passingFees[nextCity]) { dp[nextCity][nextTime] = dp[city][time] + passingFees[nextCity] q.push([nextCity, nextTime]) } } } let ans = 1e9 for (let time = 0; time <= maxTime; time++) { ans = Math.min(ans, dp[n - 1][time]) } return ans === 1e9 ? -1 : ans
好像没有很大的必要这么做,C++用数组实现邻接表主要是为了不使用 vector 加快时间。然而js没有静态数组一说,都是array😢
Example usage for LeetCode 1928