题目描述

小明的电动车电量充满时可行驶距离为 cnt，每行驶 1 单位距离消耗 1 单位电量，且花费 1 单位时间。小明想选择电动车作为代步工具。地图上共有 N 个景点，景点编号为 0 ~ N-1。他将地图信息以 [城市 A 编号, 城市 B 编号, 两城市间距离] 格式整理在在二维数组 paths，表示城市 A、B 间存在双向通路。初始状态，电动车电量为 0。每个城市都设有充电桩，charge[i] 表示第 i 个城市每充 1 单位电量需要花费的单位时间。请返回小明最少需要花费多少单位时间从起点城市 start 抵达终点城市 end。

样例

输入：
paths = [[1,3,3],[3,2,1],[2,1,3],[0,1,4],[3,0,5]]
cnt = 6, start = 1, end = 0, charge = [2,10,4,1]

输出：43

解释：最佳路线为：1->3->0。
在城市 1 仅充 3 单位电至城市 3，然后在城市 3 充 5 单位电，行驶至城市 5。
充电用时共 3*10 + 5*1= 35
行驶用时 3 + 5 = 8，此时总用时最短 43。

输入：
paths = [[0,4,2],[4,3,5],[3,0,5],[0,1,5],[3,2,4],[1,2,8]]
cnt = 8, start = 0, end = 2, charge = [4,1,1,3,2]

输出：38

解释：最佳路线为：0->4->3->2。
城市 0 充电 2 单位，行驶至城市 4 充电 8 单位，行驶至城市 3 充电 1 单位，最终行驶至城市 2。
充电用时 4*2+2*8+3*1 = 27
行驶用时 2+5+4 = 11，总用时最短 38。

限制

• 1 <= paths.length <= 200
• paths[i].length == 3
• 2 <= charge.length == n <= 100
• 0 <= path[i][0],path[i][1],start,end < n
• 1 <= cnt <= 100
• 1 <= path[i][2] <= cnt
• 1 <= charge[i] <= 100
• 题目保证所有城市相互可以到达。

算法

(单源最短路) $O((m + n \cdot cnt) \log (n \cdot cnt))$

1. 裸的单源最短路问题，将点扩展为二维，即 $(u, c)$ 表示在点 $u$，且剩余电量为 $c$ 时的最短路。
2. 起点可以定义为 $(start, 0)$。每个点都可以花费的时间去充一次电。

时间复杂度

• 总点数为 $O(n \cdot cnt)$，总边数为 $O(m + n)$。
• 若采用堆优化 Dijkstra 算法，总时间复杂度为 $O((m + n \cdot cnt) \log (n \cdot cnt))$。

空间复杂度

• 需要 $O(m + n \cdot cnt)$ 的空间存储邻接表、距离数组、以及队列。

C++ 代码 (堆优化 Dijkstra 算法)

struct Node {
    int u, c, d;
    Node(int u_, int c_, int d_):u(u_), c(c_), d(d_){}

    bool operator < (const Node &p) const {
        return d > p.d;
    }
};

class Solution {
public:
    int electricCarPlan(vector<vector<int>>& paths,
        int cnt, int start, int end, vector<int>& charge) {

        const int n = paths.size();
        vector<vector<pair<int, int>>> graph(n);
        for (const auto &p : paths) {
            graph[p[0]].push_back(make_pair(p[1], p[2]));
            graph[p[1]].push_back(make_pair(p[0], p[2]));
        }

        vector<vector<int>> dis(n, vector<int>(cnt + 1, INT_MAX));

        dis[start][0] = 0;

        priority_queue<Node> q;
        q.push(Node(start, 0, 0));

        while (!q.empty()) {
            auto sta = q.top();
            q.pop();
            int u = sta.u, c = sta.c;

            if (c + 1 <= cnt && dis[u][c + 1] > dis[u][c] + charge[u]) {
                dis[u][c + 1] = dis[u][c] + charge[u];
                q.push(Node(u, c + 1, dis[u][c + 1]));
            }

            for (const auto &v : graph[u])
                if (c >= v.second &&
                    dis[v.first][c - v.second] > dis[u][c] + v.second) {

                    dis[v.first][c - v.second] = dis[u][c] + v.second;
                    q.push(Node(v.first, c - v.second, dis[v.first][c - v.second]));
                }
        }

        int ans = INT_MAX;
        for (int i = 0; i <= cnt; i++)
            ans = min(ans, dis[end][i]);

        return ans;
    }
};

C++ 代码 (SPFA 算法)

class Solution {
public:
    int electricCarPlan(vector<vector<int>>& paths,
        int cnt, int start, int end, vector<int>& charge) {

        const int n = paths.size();
        vector<vector<pair<int, int>>> graph(n);
        for (const auto &p : paths) {
            graph[p[0]].push_back(make_pair(p[1], p[2]));
            graph[p[1]].push_back(make_pair(p[0], p[2]));
        }

        vector<vector<int>> dis(n, vector<int>(cnt + 1, INT_MAX));
        vector<vector<bool>> vis(n, vector<bool>(cnt + 1, false));
        dis[start][0] = 0;
        vis[start][0] = true;

        queue<pair<int, int>> q;
        q.push(make_pair(start, 0));

        while (!q.empty()) {
            auto sta = q.front();
            q.pop();
            int u = sta.first, c = sta.second;

            vis[u][c] = false;

            if (c + 1 <= cnt && dis[u][c + 1] > dis[u][c] + charge[u]) {
                dis[u][c + 1] = dis[u][c] + charge[u];
                if (!vis[u][c + 1]) {
                    vis[u][c + 1] = true;
                    q.push(make_pair(u, c + 1));
                }
            }

            for (const auto &v : graph[u])
                if (c >= v.second &&
                    dis[v.first][c - v.second] > dis[u][c] + v.second) {

                    dis[v.first][c - v.second] = dis[u][c] + v.second;
                    if (!vis[v.first][c - v.second]) {
                        vis[v.first][c - v.second] = true;
                        q.push(make_pair(v.first, c - v.second));
                    }
                }
        }

        int ans = INT_MAX;
        for (int i = 0; i <= cnt; i++)
            ans = min(ans, dis[end][i]);

        return ans;
    }
};