acwing::acwing853 命名空间参考

1. 有边数限制的最短路

更多...

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

详细描述

1. 有边数限制的最短路

函数说明

main()

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

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

                                              {
            int n;
            int m;
            int k;
            cin >> n >> m >> k;
            vector<tuple<int, int, int>> vec(m);
            vector shortest(n + 1, 0x3f3f3f);
            shortest[1] = 0;
            for(int i = 0; i < m; i++) {
                int x;
                int y;
                int z;
                cin >> x >> y >> z;
                vec[i] = make_tuple(x, y, z);
            }
            for(int i = 0; i < k; i++) {
                vector<int> shortest_cpy = shortest;
                for(auto [x, y, z]: vec) {
                    shortest[y] = min(shortest[y], shortest_cpy[x] + z);
                }
            }
            if(shortest[n] > 0x3f3f3f / 2) {
                cout << "impossible";
            } else {
                cout << shortest[n];
            }
            return 0;
        }

被这些函数引用 TEST() , 以及 TEST().

TEST() [1/2]

acwing::acwing853::TEST	(	acwing853	,
		case1	)

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

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

引用了 main().

TEST() [2/2]

acwing::acwing853::TEST	(	acwing853	,
		case2	)

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

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

引用了 main().