Floy算法的本质就是DP。复习一下传统的Floy算法,需要三重循环:
for(k=0;k<n;k++)
for(i=0;i<n;i++)
for(j=0;j<n;j++)
if( e[i][k]+e[k][j]<e[i][j])
e[i][j] = e[i][k]+e[k][j];在此题中,还有一个总转机次数不超过K的限制,所以除了e[i][j]表示每两个城市之间的最短距离外,还需要创建t[i][j]来存储对应e[i][j]的转机次数.于是代码转化为
for(k=0;k<n;k++)
for(i=0;i<n;i++)
for(j=0;j<n;j++)
if( e[i][k]+e[k][j]<e[i][j] && t[i][k]+t[k][j]+1<=K)
{
e[i][j] = e[i][k]+e[k][j];
t[i][j] = t[i][k]+t[k][j]+1;
}很不幸，以上的算法是错误的。周赛过后补充了一个例子：[[0,1,1],[0,2,5],[1,2,1],[2,3,1]]
当要求最多转1次（即两趟飞机），从0到3的最小代价。事实上的解是: 0->2->3，代价是5+1=6. 但是上面的算法返回的却是无解。这是因为前半段0->2的行程，floyd提前算出来的最优解是0->1->2，因为代价最小(1+1=2)，但是需要转机两次。所以再加上2->3这段时，因为转机的次数限制，被算法判断为无解。
我们可以利用dp的思想。令dp[k][b]表示从起点坐k次飞机能过够到达城市b的最小代价。显然，它之前的状态就是做k-1次飞机能到哪里。于是我们有状态转移方程：
dp[k][b] = min(dp[k][b], dp[k-1][a] + cost[a][b]), where there is a flight from a to b.
注意答案是 min(dp[k][dst]) for k=0,1,..,K+1
当然我们也可以把dp[k][b]定义成：从起点“最多”坐k次飞机能过够到达城市b的最小代价。那么对应的转移方程：
dp[b] = min(dp[k][b], dp[k-1][b], dp[k-1][a] + cost[a][b]), where there is a flight from a to b.
相应地最终答案就是 dp[K+1][dst]，不需要再遍历飞行的次数。
利用Dijkstra求最短权重路径的算法思想，可以简单的理解为基于优先队列的BFS。从起点src开始不停地做BFS，但是队列里弹出的永远是权重最小的路径（所达到的点）。这样任何弹出的点，如果是第一次到达的话，那么它一定经历的是最短路径。所以，一旦BFS的过程中遇到了终点，就可以输出它的最短代价。
但是本题不同之处在于，对于任何中转点（非终点），最短路径不一定就是最优方案，因为还有转机次数的考虑因素。举个例子，假设最多允许转机5次，一种方案是你转机3次花费10到达A地（非终点），另一种方案是转机4次花费8到达B地，对于后续的影响而言孰优孰劣我们是无法判断的。所以我们必须将它们都加入BFS的队列之中。当然，如果之前曾经以相同的转机次数到达过A，那么我们肯定只会保留最小代价的方案，所以我们需要一个visited[city][times]来记忆化之前所经历过的代价。