1976年。到着地の案件数

1976. 到達目的地の経路数 #

あなたは都市にいます。都市は $n$ 個の交差点で構成されており、交差点は $0$ から $n - 1$ までの番号が付けられています。いくつかの交差点は 双方向 の道路で接続されています。入力では、任意の交差点から他の任意の交差点に到達することができ、任意の 2 つの交差点の間には最大で 1 本の道路しかありません。

整数 $n$ と 2 次元整数配列 $roads$ が与えられます。ここで、 $roads[i] = [u_i, v_i, time_i]$ は交差点 $u_i$ と $vi$ の間に時間 $time_i$ をかけて通過する必要がある道路を表します。交差点 $0$ から交差点 $n - 1$ までの最短時間で到達するための経路数を知りたいです。

目的地に到達するためにかかる最短時間で到達するための経路数を返してください。答えが非常に大きい場合は、 $10^9 + 7$ で割った余りを返してください。

例 1：

入力：n = 7, roads = [[0,6,7],[0,1,2],[1,2,3],[1,3,3],[6,3,3],[3,5,1],[6,5,1],[2,5,1],[0,4,5],[4,6,2]]
出力：4
説明：交差点 0 から交差点 6 までの最短時間は 7 分です。
最短時間が 7 分の経路は次の4つです：
- 0 ➝ 6
- 0 ➝ 4 ➝ 6
- 0 ➝ 1 ➝ 2 ➝ 5 ➝ 6
- 0 ➝ 1 ➝ 3 ➝ 5 ➝ 6

例 2：

入力：n = 2, roads = [[1,0,10]]
出力：1
説明：交差点 0 から交差点 1 までの道路は1本だけで、10 分かかります。

ヒント：

$1 <= n <= 200$
$n - 1 <= roads.length <= n * (n - 1) / 2$
$roads[i].length == 3$
$0 <= u_i, v_i <= n - 1$
$1 <= timei <= 10^9$
$u_i \ne v_i$
任意の 2 つの交差点の間には最大で 1 本の道路があります。
任意の交差点から出発して、他の任意の交差点に到達することができます。

floyd#

class Solution {
public:
    int countPaths(int n, vector<vector<int>> &roads) {
        vector<vector<long long>> dis(n, vector<long long>(n, LLONG_MAX / 2));
        vector<vector<long long>> dp(n, vector<long long>(n));

        for (int i = 0; i < n; ++i) {
            dis[i][i] = 0;
            dp[i][i] = 1;
        }

        for (const auto &r : roads) {
            dis[r[0]][r[1]] = r[2];
            dis[r[1]][r[0]] = r[2];
            dp[r[0]][r[1]] = 1;
            dp[r[1]][r[0]] = 1;
        }

        static constexpr int mod = 1e9 + 7;
        for (int k = 0; k < n; ++k) {
            for (int i = 0; i < n; ++i) {
                for (int j = 0; j < n; ++j) {
                    if (k != i && k != j && i != j) {
                        long long sum = dis[i][k] + dis[k][j];
                        if (sum < dis[i][j]) {
                            dis[i][j] = sum;
                            dp[i][j] = dp[i][k] * dp[k][j];
                            dp[i][j] %= mod;
                        } else if (sum == dis[i][j]) {
                            dp[i][j] += dp[i][k] * dp[k][j];
                            dp[i][j] %= mod;
                        }
                    }
                }
            }
        }

        return dp[0][n - 1];
    }
};

1976年。到着地の案件数

1976. 到達目的地の経路数#

floyd#

1976. 到達目的地の経路数 #