2022年CSP-S第二轮C++真题源码解析1
10页1、2022年CSP-J第二轮真题源码解析个人解析,非评分标准答案。T1CSP-J2022假期计划【题目描述】小熊的地图上有n个点,其中编号为1的是它的家、编号2,3,.,n为的都是景点。部分点对之间有双向直达的公交线路。如果点x与z1、z1与z2、zk - 1与zk、zk与y之间均有直达的线路,那么我们称x与y之间的行程可转车k次通达;特别地,如果点x与y之间有直达的线路,则称可转车0次通达。很快就要放假了,小熊计划从家出发去个不同的景点游玩,完成5段行程后回家:家景点 A景点B景点C景点D家且每段行程最多转车k次。转车时经过的点没有任何限制,既可以是家、也可以是景点,还可以重复经过相同的点。例如,在景点A景点B 的这段行程中,转车时经过的点可以是家、也可以是景点 C,还可以是景点D家这段行程转车时经过的点。假设每个景点都有一个分数,请帮小熊规划一个行程,使得小熊访问的四个不同景点的分数之和最大。【输入格式】第一行包含三个正整数n, m, k,分别表示地图上点的个数、双向直达的点对数量、每段行程最多的转车次数。第二行包含n -1个正整数,分别表示编号为2, 3, ,n的景点的分数。接下来
2、m行,每行包含两个正整数x, y,表示点x和y之间有道路直接相连,保证1x,yn,且没有重边,自环。【输出格式】输出一个正整数,表示小熊经过的4不同景点的分数之和的最大值。【输入输出样例】输入#18 8 19 7 1 8 2 3 61 22 33 44 55 66 77 88 1输出#127输入#27 9 01 1 1 2 3 41 22 33 41 51 61 75 46 47 4输出#27【样例解释#1】当计划的行程为123571时,4个景点的分数之和为9+7+8+3=27,可以证明其为最大值。行程135781的景点分数之和为24、行程132871的景点分数之和为25。它们都符合要求,但分数之和不是最大的。行程123581的景点分数之和为30,但其中5 8至少需要转车2次,因此不符合最多转车k = 1次的要求。行程123231的景点分数之和为32,但游玩的并非4个不同的景点,因此也不符合要求。【数据范围】对于所有数据,保证 5n2500,1m10000,0k100,所有景点的分数 1si1018。保证至少存在一组符合要求的行程。参考源码1:1. #include2. usingna
3、mespacestd;3. typedeflonglongintll;4. intn,m,k;5. constintN=2505;6. intdNN;7. vectorGN;8. llscoreN;9. voidbfs(introot)10. for(inti=1;i=n;i+)drooti=-1;11. queueq;12. q.push(root),drootroot=0;13. while(q.size()14. intu=q.front();15. q.pop();16. if(drootu=k)break;17. for(intv:Gu)18. if(drootv=-1)drootv=drootu+1,q.push(v);19. 20. 21. 22. intmain()23. cinnmk;24. k+;25. for(inti=2;iscorei;27. 28. for(inti=1;ifirstNodesecondNode;31. GfirstNode.push_back(secondNode);32. GsecondNode.push_back(firstNode);
《2022年CSP-S第二轮C++真题源码解析1》由会员山不****不厌...分享,可在线阅读,更多相关《2022年CSP-S第二轮C++真题源码解析1》请在金锄头文库上搜索。
2022年CSP-S第二轮C++真题源码解析1
2022年CSP-J第二轮C++真题源码解析2
2022年CSP-J第二轮C++真题源码解析1
2022年第四届全国高校计算机能力挑战赛决赛java编程题
2021年第三届计算机能力挑战赛决赛java编程题第二套试卷
2021年第三届计算机能力挑战赛决赛java编程题第一套试卷
2022年第四届全国高校计算机能力挑战赛区域赛java编程题第一套试卷
2022年第四届全国高校计算机能力挑战赛区域赛java编程题第二套试卷
2020年第二届计算机能力挑战赛决赛java编程题第二套试卷
2020年第二届计算机能力挑战赛决赛java编程题第一套试卷
2019年第一届全国高校计算机能力挑战赛区域赛java编程题第二套试卷
2022年第四届全国高校计算机能力挑战赛(区域赛)java选择题
2019年第一届全国高校计算机能力挑战赛初赛编程题(C++)
scratch3下的九九乘法表(行优先和列优先)设计
2022年第四届全国高校计算机能力挑战赛初赛编程题(C++)
2019年第一届全国高校计算机能力挑战赛区域赛java编程题第一套试卷
2022年第四届全国高校计算机能力挑战赛决赛编程题(C++)第一套试卷
2022年第四届全国高校计算机能力挑战赛决赛编程题(C++)第二套试卷
scratch3下的汉诺塔游戏设计
2023-09-25 37页
2023-09-25 10页
2023-09-25 33页
2023-09-25 26页
2023-04-03 8页
2023-04-03 4页
2023-04-03 8页
2023-03-22 10页
2023-03-20 8页