acwing::acwing849 命名空间参考

1. Dijkstra求最短路 I

更多...

类
struct	comp

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

详细描述

1. Dijkstra求最短路 I

函数说明

main()

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

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

                                              {
            int n;
            int m;
            cin >> n >> m;
            vector<unordered_map<int, int>> vec(n + 1);
            unordered_set<int> ed;
            for(int i = 0; i < m; i++) {
                int x;
                int y;
                int z;
                cin >> x >> y >> z;
                if(vec[x][y] == 0) {
                    vec[x][y] = z;
                } else {
                    vec[x][y] = min(vec[x][y], z);
                }
            }
            priority_queue<pair<int, int>, vector<pair<int, int>>, comp> pq;
            pq.push(make_pair(1, 0));
            while(!pq.empty()) {
                auto [node, dist] = pq.top();
                pq.pop();
                if(ed.contains(node)) {
                    continue;
                }
                ed.insert(node);
                if(node == n) {
                    cout << dist;
                    return 0;
                }
                for(auto [next_node, d]: vec[node]) {
                    if(!ed.contains(next_node)) {
                        pq.push(make_pair(next_node, dist + d));
                    }
                }
            }
            cout << -1;
            return 0;
        }

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

TEST() [1/2]

acwing::acwing849::TEST	(	acwing849	,
		case1	)

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

                               {
            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::TEST	(	acwing849	,
		case2	)

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

                               {
            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().