pat::a::a1018 命名空间参考

1018 Public Bike Management 更多...

类
struct	frame
struct	frame_cmp

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

详细描述

1018 Public Bike Management

函数说明

main()

int pat::a::a1018::main	(	istream &	cin,
		ostream &	cout
	)

< the maximum capacity of each station

< the total number of stations

< the index of the problem station

< the number of roads

< the node number of bikes at Si respectively

在文件 pat.cpp 第 4712 行定义.

                                                  {
                unsigned cmax;
                unsigned n;   
                unsigned sp;  
                unsigned m;   
                auto fc = frame_cmp();
                cin >> cmax >> n >> sp >> m;
                vector c(n + 1, 0);
                for(unsigned i = 1; i <= n; i++) {
                    int ci;
                    cin >> ci;
                    c[i] = ci - static_cast<int>(cmax / 2);
                }
                vector<unordered_map<unsigned, unsigned>> g(n + 1);
                for(unsigned i = 0; i < m; i++) {
                    unsigned si, sj, tij;
                    cin >> si >> sj >> tij;
                    g[si][sj] = tij;
                    g[sj][si] = tij;
                }
                vector shortest(n + 1, -1);
                vector min_go(n + 1, -1);
                vector min_back(n + 1, -1);
                priority_queue<frame, vector<frame>, frame_cmp> pq;
                shortest[0] = 0;
                min_go[0]   = 0;
                min_back[0] = 0;
                pq.push(frame(vector<unsigned>(1, 0), 0u, 0, 0u, 0u));
                while(!pq.empty()) {
                    frame f = pq.top();
                    pq.pop();
                    if(f.node == sp) {
                        cout << f.get_go() << ' ' << f.path[0];
                        for(int i = 1; i < f.path.size(); i++) {
                            cout << "->" << f.path[i];
                        }
                        cout << ' ' << f.get_back();
                        return 0;
                    }
                    for(auto &[node, d]: g[f.node]) {
                        if(find(f.path.begin(), f.path.end(), node) == f.path.end()) {
                            //if(shortest[node] == -1 || min_go[node] == -1 || min_back[node] == -1 || fc(frame(vector<unsigned>(), node, min_back[node], shortest[node], min_go[node]), frame(vector<unsigned>(), node, f.bikes + c[node], f.len + d, f.start))) {
                            vector<unsigned> path = f.path;
                            path.emplace_back(node);
                            auto next_f = frame(path, node, f.bikes + c[node], f.len + d, f.start);
                            pq.push(next_f);
                            //shortest[node] = next_f.len;
                            //min_go[node]   = next_f.get_go();
                            //min_back[node] = next_f.get_back();
                        }
                    }
                }
                return 0;
            }

引用了 pat::a::a1018::frame::bikes, acwing::acwing861::find(), pat::a::a1018::frame::get_back(), pat::a::a1018::frame::get_go(), pat::a::a1018::frame::len, pat::a::a1018::frame::node, pat::a::a1018::frame::path , 以及 pat::a::a1018::frame::start.

被这些函数引用 TEST().

TEST() [1/3]

pat::a::a1018::TEST	(	a1018	,
		case1
	)

在文件 pat_test.cpp 第 2124 行定义.

                               {
                istringstream in("10 3 3 5\n"
                                 "6 7 0\n"
                                 "0 1 1\n"
                                 "0 2 1\n"
                                 "0 3 3\n"
                                 "1 3 1\n"
                                 "2 3 1");
                auto out = ostringstream();
                main(in, out);
                ASSERT_EQ("3 0->2->3 0", out.str());
            }

引用了 main().

TEST() [2/3]

pat::a::a1018::TEST	(	a1018	,
		case2
	)

在文件 pat_test.cpp 第 2137 行定义.

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

引用了 main().

TEST() [3/3]

pat::a::a1018::TEST	(	a1018	,
		case3
	)

在文件 pat_test.cpp 第 2152 行定义.

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

引用了 main().