Skip to content

图论 28.Floyd算法 dp数组初始化有误和建议增加测试样例 #3011

Description

@qiuyaodawo

给出的下述代码中初始化有误:

vector<vector<vector<int>>> grid(n + 1, vector<vector<int>>(n + 1, vector<int>(n + 1, 10005)));  // 因为边的最大距离是10^4

虽然单条边的长度不会超过10000,但是路径长度超过10005是可能的,事实上根据题目描述,最长路径可能是(100-1) * 10000 = 990000,故应该初始化为更大的值如1e9等。

此外,根据文章中的代码能够通过卡码网的题目,说明测试用例中没有路径长度超过10005的情形, 建议增加测试用例。

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions