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

1003 Emergency 更多...

类
struct	comp

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

详细描述

1003 Emergency

函数说明

main()

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

< shortest_cnt[i] = number of shortest path from C1 to i

< shortest[i] = shortest distance from C1 to i

< max_rescue[i] = max rescue sum from C1 to i in shortest path

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

                                                  {
                int N;
                int M;
                int C1;
                int C2;
                cin >> N >> M >> C1 >> C2;
                int max_d = 0;
                vector<int> rescue(N);
                vector grid(N, vector(N, 0));
                for(int i = 0; i < N; i++) {
                    cin >> rescue[i];
                }
                for(int i = 0; i < M; i++) {
                    int c1;
                    int c2;
                    int L;
                    cin >> c1 >> c2 >> L;
                    grid[c1][c2] = L;
                    grid[c2][c1] = L;
                    max_d += L;
                }
                vector shortest_cnt(N, 0);    
                vector shortest(N, max_d + 1);
                vector max_rescue(N, 0);      
                priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, comp> pq;
                pq.push(make_tuple(C1, 0, rescue[C1]));
                while(!pq.empty()) {
                    auto [c, d, s] = pq.top();
                    pq.pop();
                    if(d < shortest[c]) {
                        shortest[c]     = d;
                        shortest_cnt[c] = 1;
                        max_rescue[c]   = s;
                    } else if(d == shortest[c]) {
                        shortest_cnt[c]++;
                    } else {
                        continue;
                    }
                    if(s > max_rescue[c]) {
                        max_rescue[c] = s;
                    }
                    for(int i = 0; i < N; i++) {
                        if(grid[c][i] > 0 && d + grid[c][i] <= shortest[i]) {
                            pq.push(make_tuple(i, d + grid[c][i], s + rescue[i]));
                        }
                    }
                }
                cout << shortest_cnt[C2] << ' ' << max_rescue[C2];
                return 0;
            }

引用了 pat::a::a1016::M , 以及 acwing::acwing2019::N.

被这些函数引用 TEST().

TEST()

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

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

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

引用了 main().