今日安排

  • 看 图解TCP_IP 第 1 章
  • 完成算法题
  • 完成项目数据库设计和持久层编码

素养提升

完成图解TCP_IP第一章的笔记

算法小计

787. K 站中转内最便宜的航班 - 力扣（LeetCode）

【最短路/必背模板】涵盖所有的「存图方式」与「最短路算法（详尽注释）」 (qq.com)

这题是一道模板题 运用 Bellman Ford 求解有限制的最短路问题

class Solution {
    // 总时间复杂度为 O((m+n)k)
    // 空间复杂度 O(nk)
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        final int INF = 10000 * 101 + 1;;
        int[][] f = new int[k + 2][n];
        for (int i = 0; i < k + 2; i++) {
            Arrays.fill(f[i], INF);
        }
        f[0][src] = 0;
        for (int t = 1; t <= k + 1; t++) {
            for (int[] flight : flights) {
                int j = flight[0], i = flight[1], cost = flight[2];
                f[t][i] = Math.min(f[t][i], f[t - 1][j] + cost);
            }
        }
        int ans = INF;
        for (int t = 1; t <= k + 1; t++) {
            ans = Math.min(ans, f[t][dst]);
        }
        return ans == INF ? -1 : ans;
    }
}