LeetCode刷题之路 --- 787. K 站中转内最便宜的航班

 

C语言完整解法：

#define MaxValue 1000001

int findCheapestPrice(int n, int** flights, int flightsSize, int* flightsColSize, int src, int dst, int K) {

    /* 异常判断 */

    if (n < 1 || n > 100 || K < 0 || K > 10000) {

        return -1;

    }

    /* 创建数组存放结果 */

    int **dp = (int **)malloc(sizeof(int *) * n);

    for (int i = 0; i < n; i++) {

        dp[i] = (int *)malloc(sizeof(int) * (K + 1));

    }

    /* 初始化数组 */

    for (int i = 0; i < n; i++) {

        for (int j = 0; j < K + 1; j++) {

            dp[i][j] = MaxValue;

        }

    }

    /* 初始化src到src的航班 */

    for (int k = 0; k <= K; k++) {

        dp[src][k] = 0;

    }

    /* 初始化src直达的航班 */

    for (int i = 0; i < flightsSize; i++) {

        if (flights[i][0] == src) {

            dp[flights[i][1]][0] = flights[i][2];

        }

    }

    /* 动态规划 */

    for (int k = 1; k <= K; k++) {

        for (int i = 0; i < flightsSize; i++) {

            if (dp[flights[i][0]][k - 1] != MaxValue) {

                dp[flights[i][1]][k] = dp[flights[i][1]][k] > (dp[flights[i][0]][k - 1] + flights[i][2]) ? (dp[flights[i][0]][k - 1] + flights[i][2]) : dp[flights[i][1]][k];

            }

        }

    }

    return dp[dst][K] == MaxValue ? -1 : dp[dst][K];

}