acwing::acwing854 命名空间参考

1. Floyd求最短路

更多...

函数
int	main (istream &cin, ostream &cout)
	TEST (acwing854, case1)
	TEST (acwing854, case2)

详细描述

1. Floyd求最短路

函数说明

main()

int acwing::acwing854::main	(	istream &	cin,
		ostream &	cout
	)

在文件 acwing.cpp 第 7341 行定义.

                                              {
            int n;
            int m;
            int k;
            cin >> n >> m >> k;
            vector g(n + 1, vector<int>(n + 1, 1e9));
            for(int i = 0; i < m; i++) {
                int x;
                int y;
                int z;
                cin >> x >> y >> z;
                g[x][y] = min(g[x][y], z);
            }
            for(int i = 1; i <= n; i++) {
                g[i][i] = 0;
            }
            for(int l = 1; l <= n; l++) {
                for(int i = 1; i <= n; i++) {
                    for(int j = 1; j <= n; j++) {
                        g[i][j] = min(g[i][j], g[i][l] + g[l][j]);
                    }
                }
            }
            for(int i = 0; i < k; i++) {
                int x;
                int y;
                cin >> x >> y;
                if(g[x][y] > 1e9 / 2) {
                    cout << "impossible" << endl;
                } else {
                    cout << g[x][y] << endl;
                }
            }
            return 0;
        }

被这些函数引用 TEST().

TEST() [1/2]

acwing::acwing854::TEST	(	acwing854	,
		case1
	)

在文件 acwing_test.cpp 第 3437 行定义.

                               {
            istringstream in("3 3 2\n"
                             "1 2 1\n"
                             "2 3 2\n"
                             "1 3 1\n"
                             "2 1\n"
                             "1 3\n");
            auto out = ostringstream();
            main(in, out);
            const auto ans = out.str();
            ASSERT_EQ("impossible\n"
                      "1\n",
                      ans);
        }

引用了 main().

TEST() [2/2]

acwing::acwing854::TEST	(	acwing854	,
		case2
	)

在文件 acwing_test.cpp 第 3452 行定义.

                               {
            istringstream in("10 20 10\n"
                             "1 2 6\n"
                             "4 9 5\n"
                             "10 3 10\n"
                             "10 4 5\n"
                             "1 4 10\n"
                             "1 10 0\n"
                             "9 7 8\n"
                             "1 5 8\n"
                             "4 4 9\n"
                             "10 4 4\n"
                             "4 7 6\n"
                             "9 1 10\n"
                             "6 8 -3\n"
                             "2 3 10\n"
                             "2 8 1\n"
                             "7 6 6\n"
                             "4 4 5\n"
                             "8 9 8\n"
                             "6 1 8\n"
                             "6 8 7\n"
                             "7 4\n"
                             "2 10\n"
                             "4 4\n"
                             "4 1\n"
                             "8 3\n"
                             "3 7\n"
                             "10 9\n"
                             "3 10\n"
                             "6 10\n"
                             "9 5\n");
            auto out = ostringstream();
            main(in, out);
            const auto ans = out.str();
            ASSERT_EQ("18\n"
                      "19\n"
                      "0\n"
                      "15\n"
                      "28\n"
                      "impossible\n"
                      "9\n"
                      "impossible\n"
                      "8\n"
                      "18\n",
                      ans);
        }

引用了 main().