acwing::acwing852 命名空间参考

1. spfa判断负环

更多...

函数
int	main (istream &cin, ostream &cout)
bool	spfa (const vector< unordered_map< int, int > > &g, int, int n)
	TEST (acwing852, case1)
	TEST (acwing852, case2)

详细描述

1. spfa判断负环

函数说明

main()

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

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

                                              {
            int n;
            int m;
            cin >> n >> m;
            vector<unordered_map<int, int>> g(n + 1);
            vector cnt(n + 1, 0);
            vector shortest(n + 1, 0x3f3f3f);
            for(int i = 0; i < m; i++) {
                int x;
                int y;
                int z;
                cin >> x >> y >> z;
                if(g[x][y] == 0) {
                    g[x][y] = z;
                } else {
                    g[x][y] = min(g[x][y], z);
                }
            }
            for(int i = 1; i <= n; i++) {
                g[0][i] = 0;
            }
            if(spfa(g, m, n)) {
                cout << "Yes";
            } else {
                cout << "No";
            }
            return 0;
        }

引用了 spfa().

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

spfa()

bool acwing::acwing852::spfa	(	const vector< unordered_map< int, int > > &	g,
		int	,
		int	n )

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

                                                                          {
            vector cnt(n + 1, 0);
            vector shortest(n + 1, 0x3f3f3f);
            queue<int> q;
            unordered_set<int> us;
            q.push(0);
            us.insert(0);
            shortest[0] = 0;
            while(!q.empty()) {
                int node = q.front();
                q.pop();
                us.erase(node);
                for(auto [next_node, d]: g[node]) {
                    if(shortest[next_node] > shortest[node] + d) {
                        shortest[next_node] = shortest[node] + d;
                        cnt[next_node]      = cnt[node] + 1;
                        if(cnt[next_node] >= n + 1) {
                            return true;
                        }
                        if(!us.contains(next_node)) {
                            q.push(next_node);
                            us.insert(next_node);
                        }
                    }
                }
            }
            return false;
        }

引用了 spfa().

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

TEST() [1/2]

acwing::acwing852::TEST	(	acwing852	,
		case1	)

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

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

引用了 main().

TEST() [2/2]

acwing::acwing852::TEST	(	acwing852	,
		case2	)

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

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

引用了 main().