问题

LeetCode #787

在单源最短路径问题的基础上，加一条限制，最多只能通过K个点中转，或说最多只能通过K+1条边。

解决

除了Dijkstra之外，还有一个单源最短路径算法，叫做Bellman-Ford算法。离散教材上用它来解决带有负权边的单源最短路径问题。事实上，它也可以解决这种限制了最多中转次数的问题。

Bellman-Ford算法的原型在此不做赘述了，其核心就是迭代，没迭代一次相当于从源点向外走了一步，有一点像BFS。而这个过程略作改造就可以解决本问题。原型核心代码如下：

while (true)
{
    bool changed = 0;
    for (int i = 0; i < n; i++)
    {
        // j -> i
        for (int j = 0; j < n; j++)
        {
            if (graph[j][i] < inf && ans[i] > bak_ans[j] + graph[j][i])
            {
                ans[i] = bak_ans[j] + graph[j][i];
                changed = 1;
            }
        }
    }
    if (!changed)
        break;
}

为什么要改造呢？因为我们现在要求每一步迭代（即while中的部分）只能走一步。而假想一个图，1->2，2->3，1->3，求1->3的单源最短路径，第一次迭代中，ans[2]被更新（相当于从1到2），紧接着ans[3]借着刚刚更新的ans[2]被更新（相当于从2到3），即这一次迭代中走了两步。（如果1->3的距离大于1->2加2->3的距离，那么第一次迭代之后保留的就是后者。）如果是这样的话，我们就没法通过控制迭代次数来控制最多走多少边了。因此，我们不能让ans[3]更新时享用同一次迭代中ans[2]刚刚更新的数值，而只能让它用上一轮迭代后的数值，这样一次迭代就只能走一步了。

于是，只要做一个数据分离就可以解决一次迭代走多步的问题了。修改后（把while循环改成了对k的循环），很容易得到完整的代码如下，实现了最多走K+1条边，或说最多通过K个点转移的效果。

class Solution
{
public:
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K)
    {
        // bellman-ford
        int graph[100][100] = { 0 };
        memset(graph, 0x3f, sizeof(graph));
        const int inf = 60000000;
        for (auto iter : flights)
        {
            graph[iter[0]][iter[1]] = iter[2];
        }
        int ans[100] = { 0 };
        memset(ans, 0x3f, sizeof(ans));
        ans[src] = 0;
        for (int k = 1; k <= K + 1; k++)
        {
            bool changed = 0;
            int bak_ans[100] = { 0 };
            for (int i = 0; i < n; i++)
                bak_ans[i] = ans[i];
            for (int i = 0; i < n; i++)
            {
                // j -> i
                for (int j = 0; j < n; j++)
                {
                    if (graph[j][i] < inf && ans[i] > bak_ans[j] + graph[j][i])
                    {
                        ans[i] = bak_ans[j] + graph[j][i];
                        changed = 1;
                    }
                }
            }
            if (!changed)
                break;
        }
        int res = ans[dst] < inf ? ans[dst] : -1;
        return res;
    }
};