首页/新闻资讯/正文详情

P1529 回家 Bessie Come Home【洛谷算法习题】

发布时间:2026/11/21 11:12:20 来源:云帆数科 栏目:资讯中心
P1529 回家 Bessie Come Home【洛谷算法习题】
P1529 回家 Bessie Come Home网页链接P1529 回家 Bessie Come Home题目描述现在是晚餐时间而母牛们在外面分散的牧场中。Farmer John 按响了电铃所以她们开始向谷仓走去。 你的工作是要指出哪只母牛会最先到达谷仓在给出的测试数据中总会有且只有一只最快的母牛。在挤奶的时候晚餐前每只母牛都在她自己的牧场上一些牧场上可能没有母牛。每个牧场由一条条道路和一个或多个牧场连接可能包括自己。有时两个牧场可能是字母相同的之间会有超过一条道路相连。至少有一个牧场和谷仓之间有道路连接。因此所有的母牛最后都能到达谷仓并且母牛总是走最短的路径。当然母牛能向着任意一方向前进并且她们以相同的速度前进。牧场被标记为a … z \texttt{a} \ldots \texttt{z}a…z和A … Y \texttt{A} \ldots \texttt{Y}A…Y在用大写字母表示的牧场中有一只母牛小写字母中则没有。 谷仓的标记是Z \texttt{Z}Z注意没有母牛在谷仓中。注意m \texttt{m}m和M \texttt{M}M不是同一个牧场。输入格式第一行一个整数P PP1 ≤ P ≤ 10 4 1\leq P \leq 10^41≤P≤104表示连接牧场谷仓的道路的数目。接下来P PP行每行用空格分开的两个字母和一个正整数被道路连接牧场的标号和道路的长度道路长度均不超过10 3 10^3103。输出格式单独的一行包含二个项目最先到达谷仓的母牛所在的牧场的标号和这只母牛走过的路径的长度。输入输出样例 #1输入 #15 A d 6 B d 3 C e 9 d Z 8 e Z 3输出 #1B 11说明/提示翻译来自 NOCOWUSACO 2.4解题思路本题是多源最短路问题母牛分布在部分大写字母标记的牧场谷仓位于Z。目标是在所有有牛的牧场中找到到达Z最短路径长度及对应的牧场。由于节点数极少最多 52 个牧场采用 Floyd-Warshall 全源最短路直接求解。1. 问题建模节点与边牧场用字母A~Z和a~z标记共52 5252个节点。谷仓是Z。道路是无向边有长度两个牧场之间可能有多条道路取最小值。有牛标记大写的A~Y牧场中可能有一只母牛题目保证至少一只且只有一只最快。Z是谷仓无牛。目标在所有p[i]1即有牛的大写字母节点中找出到Z最短路径的节点及其距离。2. 算法实现初始化邻接矩阵a [ 256 ] [ 256 ] a[256][256]a[256][256]存储任意两点间的最短距离对角线为0 00其余初始化为一个极大值10 8 10^8108。读入与建图读取边数n nn。每行读取两个字母和一个正整数长度。若字母是大写标记p[字母]1。更新a [ A ] [ B ] a[A][B]a[A][B]和a [ B ] [ A ] a[B][A]a[B][A]为当前存储值与输入长度的较小值处理重边。Floyd-Warshall 全源最短路三层循环中间节点k kk起点i ii终点j jj覆盖A到z的所有字母。松弛操作若a [ i ] [ j ] a [ i ] [ k ] a [ k ] [ j ] a[i][j] a[i][k] a[k][j]a[i][j]a[i][k]a[k][j]则更新。寻找最优母牛遍历大写字母A到Y如果该节点有牛且a [ i ] [ ′ Z ′ ] a[i][Z]a[i][′Z′]小于当前最小值更新最小距离m mm和牧场标号h e hehe。输出输出牧场标号和最短距离。3. 复杂度分析时间复杂度Floyd-Warshall 的节点数V 52 V52V52复杂度O ( V 3 ) ≈ 1.4 × 10 5 O(V^3) \approx 1.4 \times 10^5O(V3)≈1.4×105对于P ≤ 10 4 P \le 10^4P≤104条边完全可行。空间复杂度O ( V 2 ) O(V^2)O(V2)邻接矩阵仅需256 × 256 256 \times 256256×256个long long空间极小。总结将字母牧场映射为图的节点无向边带权用 Floyd 算法求出所有牧场间最短路径再遍历有牛的大写牧场取到Z的最小距离者即为答案。注意处理重边取最小值区分大小写节点即可。代码简要说明全局数组a[256][256]邻接矩阵存储最短距离。p[256]标记大写字母牧场是否有牛。初始化与输入所有i≠j的a [ i ] [ j ] a[i][j]a[i][j]初始化为10 8 10^8108。用scanf读取边更新矩阵并标记有牛的节点。Floyd 核心三层循环遍历所有字母更新a[i][j] min(a[i][j], a[i][k]a[k][j])。结果查找与输出遍历A~Y找到有牛且距离Z最短的节点输出字符和距离。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;ll a[256][256]{0};ll p[256]{0};ll n,i,j,k;charA,B;intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);scanf(%lld\n,n);for(iA;iz;i)for(jA;jz;j)if(i!j)a[i][j]100000000;for(i1;in;i){ll haha;scanf(%c %c %lld\n,A,B,haha);if(AAAZ)p[A]1;if(BABZ)p[B]1;a[A][B]min(a[A][B],haha);a[B][A]min(a[A][B],a[B][A]);}for(kA;kz;k)for(iA;iz;i)for(jA;jz;j)if(a[i][j]a[i][k]a[k][j])a[i][j]a[i][k]a[k][j];ll m100000000;charhe;for(iA;iY;i)if((p[i]1)(a[i][Z]m)){ma[i][Z];he(char)i;}couthe mendl;return0;}

相关推荐

AI-Shoujo HF Patch:终极游戏增强补丁完全指南
AI-Shoujo HF Patch:终极游戏增强补丁完全指南

AI-Shoujo HF Patch:终极游戏增强补丁完全指南 【免费下载链接】AI-HF_Patch Automatically translate, uncensor and update AI-Shoujo! 项目地址: https://gitcode.com/gh_mirrors/ai/AI-HF_Patch 你是否正在寻找一款能够彻底改变AI-Shoujo游戏体验的强大工… · 2026/11/2 0:13:30

Obsidian手写笔记插件终极指南:3步实现PDF自由标注的完整解决方案
Obsidian手写笔记插件终极指南:3步实现PDF自由标注的完整解决方案

Obsidian手写笔记插件终极指南:3步实现PDF自由标注的完整解决方案 【免费下载链接】obsidian-handwritten-notes Obsidian Handwritten Notes Plugin 项目地址: https://gitcode.com/gh_mirrors/ob/obsidian-handwritten-notes 你是否经常在Obsidian中阅读PD… · 2026/9/21 2:47:24

Havenlon|AI 时代的执行安全语言体系(四二):Propose、Confirm 与 Commit
Havenlon|AI 时代的执行安全语言体系(四二):Propose、Confirm 与 Commit

Working Draft AI Era Execution Security LanguageThis article is part of the Havenlon Execution Security Language project. The terminology and definitions presented here describe the current working draft and may evolve as the discipline matures.AI 时代执行… · 2026/9/20 2:41:58

兰州特种工退休金怎么报名?工地太忙根本没时间复习考试
兰州特种工退休金怎么报名?工地太忙根本没时间复习考试

兰州特种工退休金怎么报名?工地太忙根本没时间复习考试 工地太忙根本没时间复习考试,这是很多兰州特种工兄弟的共同困扰。特别是那些长期奋战在一线的电焊工、电工、高处作业人员,不仅工作强度大,还要面对频繁的复审和继续教育,时间一长,很多人的证书都… · 2026/11/21 11:11:31

三墩附近考电工证怎么报名?学历不高怕报不上名?网上查询教你一步搞定
三墩附近考电工证怎么报名?学历不高怕报不上名?网上查询教你一步搞定

三墩附近考电工证怎么报名?学历不高怕报不上名?网上查询教你一步搞定 你是不是学历不高,担心自己报不了电工证?其实,三墩附近考电工证的门槛并不高,关键是你得知道怎么 网上查询… · 2026/11/21 11:11:31

鹤壁电工证补贴怎么申请?网上查询全攻略来了
鹤壁电工证补贴怎么申请?网上查询全攻略来了

鹤壁电工证补贴怎么申请?网上查询全攻略来了 学历不高怕报不上名?其实鹤壁电工证补贴申请门槛并没有想象中那么高,关键是你有没有掌握正确的报名方式和材料准备方法。最近有不少人问我“网上查询”怎么操作,今天就来聊聊鹤壁电工证补贴申请的那些事,特别… · 2026/11/21 11:11:31

低压电工证操作证查询怎么补办?多少钱?手把手教你全流程
低压电工证操作证查询怎么补办?多少钱?手把手教你全流程

低压电工证操作证查询怎么补办?多少钱?手把手教你全流程 证书过期了不知道怎么复审延期?你不是一个人,这几乎是每个低压电工从业者的“心头病”。尤其是像你这样在濮阳工作,可能因转岗、跨省流动,导致证书信息不连贯、办理流程不熟悉。今天就用最接地气… · 2026/11/21 11:11:31

电工证复审有补贴么?良心建议帮你避开报名陷阱
电工证复审有补贴么?良心建议帮你避开报名陷阱

电工证复审有补贴么?良心建议帮你避开报名陷阱 你是不是也在纠结,电工证复审到底有没有补贴?去哪里报名才能不被中介坑?别急,我来给你讲讲真实案例,手把手带你避坑。 案例背景:一名河南电工的复审经历… · 2026/11/21 11:11:31

电工证快速办理 洛阳电子证书怎么转异地
电工证快速办理 洛阳电子证书怎么转异地

电工证快速办理 洛阳电子证书怎么转异地 证书过期了不知道怎么复审延期,这事儿你肯定经历过,也肯定不想再经历一次。尤其是在洛阳,很多电工从业者在操作过程中,因为没及时复审,不仅面临被单位追责,还可能被列入黑名单,影响后续就业。别急,咱们今天就… · 2026/11/21 11:10:31

长春初级电工证怎么考?通过率揭秘全在这里
长春初级电工证怎么考?通过率揭秘全在这里

长春初级电工证怎么考?通过率揭秘全在这里 之前考的证在外省能不能转过来?这几乎是每个想从事电工工作的人都会问的问题。特别是那些在外地打拼多年、手里握着一张“外地电工证”的人,到了长春想继续干这一行,第一反应就是“我的证能用吗?”。今天我们就… · 2026/11/20 16:18:19

国内电工证报考条件与考试时间
国内电工证报考条件与考试时间

低压电工证怎么考?学历不高也能报名,官方报名入口全在这 你是不是经常听说“电工证是入行门槛”,但又担心自己学历不够、经验不足,根本报不了名?别急,今天就带你从零了解【国内电工证】的报考流程、考试内容,还有怎么在 官方报名入口… · 2026/11/20 18:25:07

电工作业时如何断电?电子证书到底能不能全国通用?
电工作业时如何断电?电子证书到底能不能全国通用?

电工作业时如何断电?电子证书到底能不能全国通用? 实操考试心里没底怕挂科,特别是电工作业时如何断电这一操作,不仅关系到你能不能拿到证书,更关系到以后能不能顺利上岗。很多人觉得这不过就是“断个电”,但其实这里面的门道可不少,稍有不慎就可能出错… · 2026/11/20 17:56:32

电工证征求意见2026河南最新政策怎么应对?学历不高也能考!
电工证征求意见2026河南最新政策怎么应对?学历不高也能考!

电工证征求意见2026河南最新政策怎么应对?学历不高也能考! 你是不是也担心自己学历不高, 怕报不上名 ?尤其是像焦作水利工程这样的从业者,常年在一线作业,但证书却成了晋升、转岗、接项目的关键门槛。 2026河南最新政策… · 2026/11/21 0:00:17

电工证征求意见怎么填?含金量高不高?济源电工朋友看过来
电工证征求意见怎么填?含金量高不高?济源电工朋友看过来

电工证征求意见怎么填?含金量高不高?济源电工朋友看过来 不知道去哪报名怕被中介坑,电工证征求意见填错了不仅白费钱,还可能影响后续考试和工作。最近很多济源的电工朋友都在问: 电工证征求意见怎么填… · 2026/11/21 0:00:17

房建企业特种工考前押题怎么找?别让培训费打了水漂
房建企业特种工考前押题怎么找?别让培训费打了水漂

房建企业特种工考前押题怎么找?别让培训费打了水漂 怕考不过白交培训费?房建企业特种工考试难度高、题型多,很多人报名后才发现没有合适的复习资料,最终考试落榜,白白浪费了时间和金钱。别担心,掌握【考前押题】的技巧,能让你事半功倍,顺利通过考试。… · 2026/11/21 0:00:17

双极步进电机控制实战:DRV8818PWPR与PIC18F86K22驱动调试
双极步进电机控制实战:DRV8818PWPR与PIC18F86K22驱动调试

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/20 10:25:45

STM32F207ZG + DRV8818PWPR 步进电机驱动实战解析
STM32F207ZG + DRV8818PWPR 步进电机驱动实战解析

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/20 10:25:54

DRV8818PWPR+dsPIC30F4013工业级双极步进电机控制方案
DRV8818PWPR+dsPIC30F4013工业级双极步进电机控制方案

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/20 10:26:03

了解更多?预约专属演示

我们的顾问将为您一对一讲解产品与方案

企业微信二维码