P9751 [CSP-J 2023] 旅游巴士一题的题解

发布时间:2026/9/30 19:30:27
P9751 [CSP-J 2023] 旅游巴士一题的题解 35分观察到有六七个点ai0我们选择直接无视其他点假装小z进入景区时所有道路都能通行了那么问题就转换成一个简单的广搜了用一个队列一层一层的把景点压入当到了终点时就是最省时间的了。#includebits/stdc.husingnamespacestd;intn,m,k;vectorpairint,intg[10005];boolvis[10005][10005];voidbfs(){queuepairint,intq;q.push({1,0});while(!q.empty()){intuq.front().first;inttq.front().second;q.pop();if(unt%k0){coutt;return;}if(vis[u][t%k])continue;vis[u][t%k]1;for(inti0;ig[u].size();i){q.push({g[u][i].first,t1});}}cout-1;return;}intmain(){cinnmk;while(m--){intu,v,w;cinuvw;g[u].push_back({v,w});}bfs();return0;}正解单源最短路可以用dijkstra来做。(这里给大家一个学迪杰斯特拉的网址我老师推荐的https://www.bilibili.com/video/BV1uT4y1p7Jy/?spm_id_from333.337.search-card.all.clickvd_sourceb59c08196148ea3ea8a331da551bf5a8总而言之dijkstra可以在中间添加路开通的时间判断能否走下一步找最短时间。#includebits/stdc.husingnamespacestd;intn,m,k,ans1e9;vectorvectorpairint,intg;boolvis[10005][105];voiddijkstra(){priority_queuepairint,int,vectorpairint,int,greaterpairint,intq;//建立小根堆维护最短路径q.push({0,1});while(!q.empty()){pairint,intcurq.top();q.pop();inttcur.first;intucur.second;if(unt%k0){ansmin(ans,t);}if(vis[u][t%k])continue;vis[u][t%k]1;for(inti0;ig[u].size();i){intvg[u][i].first;intwg[u][i].second;intntt1;if(ntw){nt(w-ntk)/k*k;}q.push({nt,v});}}}intmain(){cinnmk;g.resize(n1);for(inti1;im;i){intu,v,w;cinuvw;g[u].push_back({v,w});}dijkstra();if(ans1e9)cout-1;elsecoutans;return0;}

关于本文作者

来自尧图内容编辑团队

尧图内容编辑团队 内容团队

尧图内容编辑团队

本文由尧图网络内容编辑团队执笔。团队由资深项目经理、前端工程师与设计师组成,所有内容均来自亲手交付的真实项目,先讲清问题、再给出可落地的解法。尧图深耕北京网站建设十年,服务过京华建材集团、智造科技等各行业客户,把一线经验沉淀为可复用的行业观察。

  • 十年建站经验,覆盖建材、制造、服务、文创等
  • 项目经理把关选题与事实准确性
  • 工程师与设计师联合撰写专业细节
  • 统一编辑规范,保证文风与排版一致
  • 每月复盘转化数据,迭代选题方向

延伸阅读

相关资讯与近期热门内容

深度阅读推荐

建站决策前值得细读的三篇

网站改版的5个关键决策
2024-08-12

网站改版的5个关键决策

什么时候该改版、改到什么程度、如何避免流量掉光,京华建材集团改版复盘给出答案。

获取专属建站方案

看完文章,把您的行业与预算告诉我们,免费获取一份量身定制的官网建设方案与报价。

立即免费咨询