近似最短路径 (8)

今天来写点杂记和更多的 Leetcode :)

11.7 把树对应到 Hamming Distance

距离标签是个有趣的概念，如果想要让计算距离的过程更加简化，可以考虑将距离标签想像成赋距空间(metric space)内的某个点。今天来想想看一个简单的脑力激荡：把一棵树的节点建立一个二元字串，使得两个节点之间的距离恰好是这两个点标签中，不同的字元数量。

我们可以将每个点给一个长度为 n-1 的二元字串：每一个字元对应到树上的一条边，这条边可以把树切成两半，我们可以把其中一半的点对应到 0 这个字元、另一半的点对应到 1 这个字元。那麽，对於树上任两点，其对应到的字串之间的相异字元位置，恰好就对应到这两点之间的路径上的那些边。

11.8 更多的 Leetcode

Leetcode 1928. Minimum Cost to Reach Destination in Time

https://leetcode.com/problems/minimum-cost-to-reach-destination-in-time/
题目大意：地图上有N座城镇，你想要从编号 0 走到编号 N-1 的城镇。每经过一个城镇(包含起讫点)都需要收 passingFees[i] 的费用。每条双向道路都有一个旅行需要的时间。求旅行时间不超过 maxTime 的所有路线中，总花费最少的费用。(maxTime <= 1000; N <= 1000)
解题思考：这题可以用动态规划。我们利用 dp(t, x) 表示到达位置 x 使用总时间 t 需要的最少花费。注意到所有旅行时间都是正整数，因此可以从小的 t 到大的 t 逐步进行动态规划。

class Solution {
public:
    int minCost(int maxTime, vector<vector<int>>& edges, vector<int>& passingFees) {
        int n = passingFees.size();
        int m = edges.size();
        int dp[1005][1005];
        memset(dp, -1, sizeof(dp));
        vector<vector<int>> adj(n);
        for (int i = 0; i < m; i++) {
            adj[edges[i][0]].push_back(i);
            adj[edges[i][1]].push_back(i);
        }
        
        dp[0][0] = passingFees[0];
        for (int t = 0; t <= maxTime; t++) {
            for (int x = 0; x < n; x++) {
                if (t > 0 && dp[t-1][x] != -1 && (dp[t][x] == -1 || dp[t][x] > dp[t-1][x])) dp[t][x] = dp[t-1][x];
                if (dp[t][x] != -1 && (t == 0 || dp[t][x] != dp[t-1][x])) {
                    for (int i : adj[x]) {
                        int y = edges[i][0] + edges[i][1] - x;
                        int z = t + edges[i][2];
                        int c = dp[t][x] + passingFees[y];
                        if (z <= maxTime && (dp[z][y] == -1 || dp[z][y] > c)) {
                            dp[z][y] = c;
                        }
                    }
                }
            }
        }
        
        int minCost = -1;
        for (int t = 0; t <= maxTime; t++) {
            if (dp[t][n-1] != -1 && (minCost == -1 || minCost > dp[t][n-1]))
                minCost = dp[t][n-1];
        }
        return minCost;
        
    }
};