acwing::acwing849_408 命名空间参考

1. Dijkstra求最短路 I

更多...

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

详细描述

1. Dijkstra求最短路 I

函数说明

main()

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

在文件 acwing408.cpp 第 764 行定义.

                                              {
            int n, m;
            cin >> n >> m;
            unordered_map<int, unordered_map<int, int>> g = unordered_map<int, unordered_map<int, int>>();
            unordered_set<int> visited                    = unordered_set<int>();
            while(m--) {
                int x, y, z;
                cin >> x >> y >> z;
                if(g[x].count(y) == 0 || g[x][y] > z) {
                    g[x][y] = z;// Only keep the smallest weight for multiple edges
                }
            }
            visited.insert(1);
            // Custom comparator for priority_queue to prioritize smaller weights
            auto cmp = [](pair<int, int> left, pair<int, int> right) {
                return left.second > right.second;// Compare by distance
            };
            priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> pq(cmp);
            pq.emplace(1, 0);
            while(!pq.empty()) {
                auto [u, d] = pq.top();
                pq.pop();
                if(u != 1 && (visited.find(u) != visited.end()))
                    continue;
                visited.insert(u);
                if(u == n) {
                    cout << d;
                    return 0;
                }
                for(auto [v, w]: g[u]) {
                    if(visited.find(v) != visited.end())
                        continue;
                    pq.emplace(v, d + w);
                }
            }
            cout << -1;
            return 0;
        }

引用了 acwing::acwing4397::cmp(), acwing::acwing1929::left , 以及 acwing::acwing1929::right.

被这些函数引用 TEST().

TEST() [1/2]

acwing::acwing849_408::TEST	(	acwing849_408	,
		case1
	)

在文件 acwing408_test.cpp 第 1150 行定义.

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

引用了 main().

TEST() [2/2]

acwing::acwing849_408::TEST	(	acwing849_408	,
		case2
	)

在文件 acwing408_test.cpp 第 1161 行定义.

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

引用了 main().