Bessie Come Home回家 NOIP题解

这篇具有很好参考价值的文章主要介绍了Bessie Come Home回家 NOIP题解。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

Bessie Come Home回家

(comehome.pas)

【问题描述】

现在是晚餐时间,而母牛们在外面分散的牧场中。农民约翰按响了电铃,所以她们开始向谷仓走去。你的工作是要指出哪只母牛会最先到达谷仓(在给出的测试数据中,总会有且只有一只最快的母牛)。在挤奶的时候(晚餐前),每只母牛都在她自己的牧场上,一些牧场上可能没有母牛。每个牧场由一条条道路和一个或多个牧场连接(可能包括自己)。有时,两个牧场(可能是字母相同的)之间会有超过一条道路相连。至少有一个牧场和谷仓之间有道路连接。因此,所有的母牛最后都能到达谷仓,并且母牛总是走最短的路径。当然,母牛能向着任意一方向前进,并且她们以相同的速度前进。牧场被标记为'a'..'z'和'A'..'Y',在用大写字母表示的牧场中有一只母牛,小写字母中则没有。谷仓的标记是'Z',注意没有母牛在谷仓中。

注意'm'和'M'不是同一个牧场 否则错误 上面的意思是说:输入数据中可能会同时存在M,m(郁闷ing),比如 

M a a m m z 

【输入格式】(comehome.in) 

第 1 行: 整数 P(1<= P<=10000),表示连接牧场(谷仓)的道路的数目。

第 2 ..P+1行: 用空格分开的两个字母和一个整数: 

被道路连接牧场的标记和道路的长度(1<=长度<=1000)。 

【输出格式】(comehome.out) 

单独的一行包含二个项目: 最先到达谷仓的母牛所在的牧场的标记,和这只母牛走过的路径的长度。

【样例输入】(comehome.in) 

5

A d 6

B d 3

C e 9

d Z 8

e Z 3

【样例输出】

B 11

【思路分析】

 此题可以简化为一个求最短路的算法:

     把‘Z’ 点当做一个根节点然后用迪斯卡尔算法求到每一个‘A'..’Y' 中最小值即可!!

【参考程序】文章来源地址https://www.toymoban.com/news/detail-668016.html

var dist:array['A'..'z','A'..'z'] of longint;
    n,m,max,d,min:longint;
    v:array['A'..'z'] of boolean;
    vv:array['A'..'Z'] of boolean;
    i,j,k:char;
    ch1,ch2,ch:char;
begin
  assign(input,'comehome.in');reset(input);
  assign(output,'comehome.out');rewrite(output);
  readln(n);
   fillchar(vv,sizeof(vv),false);
   fillchar(v,sizeof(v),false);
   for d:=1 to n do
    begin
     readln(ch1,ch,ch2,min);
     if (dist[ch1,ch2]<>0)and(dist[ch1,ch2]<min) then  dist[ch1,ch2]:=dist[ch1,ch2];
     if (dist[ch1,ch2]<>0)and(dist[ch1,ch2]>min) then  dist[ch1,ch2]:=min;
     if dist[ch1,ch2]=0 then dist[ch1,ch2]:=min;
     dist[ch2,ch1]:=dist[ch1,ch2];
     if (ch1>='A')and(ch1<='Z') then
      vv[ch1]:=true;
    end;
   v['Z']:=true;
   for i:='A' to 'z' do
    begin
      if (ord(i)>90)and(ord(i)<97) then continue;
       max:=maxlongint;
      for j:='A' to 'z' do
        if (dist['Z',j]<>0)and(dist['Z',j]<max)and(not v[j]) then
         begin
          max:=dist['Z',j];
          k:=j;
         end;
      v[k]:=true;
     for j:='A' to 'z' do
      if dist[k,j]>0 then
       if (dist['Z',k]+dist[k,j]<dist['Z',j])or(dist['Z',j]=0) then
        dist['Z',j]:=dist['Z',k]+dist[k,j];
    end;
     min:=maxlongint;
   for i:='A' to 'Y' do
   if vv[i] then
    begin
     if (dist['Z',i]<min)and(dist['Z',i]<>0) then
      begin
       k:=i;
       min:=dist['Z',i];
      end;
    end;
  writeln(k,' ',min);
 close(input); close(output);
end.

到了这里,关于Bessie Come Home回家 NOIP题解的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • P1077 [NOIP2012 普及组] 摆花 题解

    小明的花店新开张,为了吸引顾客,他想在花店的门口摆上一排花,共 m m m 盆。通过调查顾客的喜好,小明列出了顾客最喜欢的 n n n 种花,从 1 1 1 到 n n n 标号。为了在门口展出更多种花,规定第 i i i 种花不能超过 a i a_i a i ​ 盆,摆花时同一种花放在一起,且不同种类的花

    2024年02月08日
    浏览(48)
  • P1967 [NOIP2013 提高组] 货车运输 题解

    原题地址 由于题目要求的是使两点之间的最小边权最大,所以可以构造最大生成树(最大生成树一定是最大瓶颈生成树,而瓶颈生成树上两点之间的路径,在原图中的所有路径中,最小边权仍然最大,即满足题目要求,详见 https://oi-wiki.org/graph/mst/#瓶颈生成树 ),答案为最大

    2024年04月08日
    浏览(40)
  • 【洛谷 P1097】[NOIP2007 提高组] 统计数字 题解(映射)

    注意 :数据可能存在加强。 某次科研调查时得到了 n n n 个自然数,每个数均不超过 1.5 × 1 0 9 1.5 times 10^9 1.5 × 1 0 9 。已知不相同的数不超过 1 0 4 10^4 1 0 4 个,现在需要统计这些自然数各自出现的次数,并按照自然数从小到大的顺序输出统计结果。 共 n + 1 n+1 n + 1 行。 第一

    2024年02月09日
    浏览(48)
  • P1024 [NOIP2001 提高组] 一元三次方程求解题解

    题目 有形如: 这样的一个一元三次方程。给出该方程中各项的系数(a,b,c,d均为实数),并约定该方程存在三个不同实根(根的范围在−100至100之间),且根与根之差的绝对值≥1。要求由小到大依次在同一行输出这三个实根(根与根之间留有空格),并精确到小数点后2位。 提

    2024年02月20日
    浏览(42)
  • 题解 洛谷P1088 [NOIP2004 普及组] 火星人——【C/C++】

    人类终于登上了火星的土地并且见到了神秘的火星人。人类和火星人都无法理解对方的语言,但是我们的科学家发明了一种用数字交流的方法。这种交流方法是这样的,首先,火星人把一个非常大的数字告诉人类科学家,科学家破解这个数字的含义后,再把一个很小的数字加

    2024年01月25日
    浏览(36)
  • 【洛谷 P1328】[NOIP2014 提高组] 生活大爆炸版石头剪刀布 题解(模拟+向量)

    石头剪刀布是常见的猜拳游戏:石头胜剪刀,剪刀胜布,布胜石头。如果两个人出拳一样,则不分胜负。在《生活大爆炸》第二季第 8 集中出现了一种石头剪刀布的升级版游戏。 升级版游戏在传统的石头剪刀布游戏的基础上,增加了两个新手势: 斯波克:《星际迷航》主角之一。 蜥

    2024年02月09日
    浏览(40)
  • 【洛谷 P1024】[NOIP2001 提高组] 一元三次方程求解 题解(数学+二分答案)

    有形如: a x 3 + b x 2 + c x + d = 0 a x^3 + b x^2 + c x + d = 0 a x 3 + b x 2 + c x + d = 0 这样的一个一元三次方程。给出该方程中各项的系数( a , b , c , d a,b,c,d a , b , c , d 均为实数),并约定该方程存在三个不同实根(根的范围在 − 100 -100 − 100 至 100 100 100 之间),且根与根之差的绝对值

    2024年02月06日
    浏览(36)
  • 【洛谷 P1029】[NOIP2001 普及组] 最大公约数和最小公倍数问题 题解(更相减损术)

    输入两个正整数 x 0 , y 0 x_0, y_0 x 0 ​ , y 0 ​ ,求出满足下列条件的 P , Q P, Q P , Q 的个数: P , Q P,Q P , Q 是正整数。 要求 P , Q P, Q P , Q 以 x 0 x_0 x 0 ​ 为最大公约数,以 y 0 y_0 y 0 ​ 为最小公倍数。 试求:满足条件的所有可能的 P , Q P, Q P , Q 的个数。 一行两个正整数 x 0 , y 0

    2024年02月09日
    浏览(44)
  • 【LeetCode】数据结构题解(6)[回文链表]

    所属专栏:玩转数据结构题型 博主首页:初阳785 代码托管:chuyang785 感谢大家的支持,您的点赞和关注是对我最大的支持!!! 博主也会更加的努力,创作出更优质的博文!! 关注我,关注我,关注我,重要的事情说三遍!!!!!!!! 回文链表 给定一个链表的 头节点

    2024年02月03日
    浏览(48)
  • 【LeetCode】数据结构题解(5)[分割链表]

    所属专栏:玩转数据结构题型 博主首页:初阳785 代码托管:chuyang785 感谢大家的支持,您的点赞和关注是对我最大的支持!!! 博主也会更加的努力,创作出更优质的博文!! 关注我,关注我,关注我,重要的事情说三遍!!!!!!!! 分割链表 给你一个链表的头节点

    2024年02月04日
    浏览(49)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包