链接:hdu1233
Description
- 某省调查乡村交通状况,得到的统计表中列出了任意两村庄间的距离。省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路
- 交通(但不一定有直接的公路相连,只要能间接通过公路可达即可),并要求铺设的公路总长度为最小。请计算最小的公路总长度。
learn
链接:poj2253
- Freddy Frog is sitting on a stone in the middle of a lake. Suddenly he notices Fiona Frog who is sitting on
- another stone. He plans to visit her, but since the water is dirty and full of tourists’ sunscreen, he wants
- to avoid swimming and instead reach her by jumping.
- Unfortunately Fiona’s stone is out of his jump range. Therefore Freddy considers to use other stones as
- intermediate stops and reach her by a sequence of several small jumps.
- To execute a given sequence of jumps, a frog’s jump range obviously must be at least as long as the longest
- jump occuring in the sequence.
- The frog distance (humans also call it minimax distance) between two stones therefore is defined as the
minimum necessary jump range over all possible paths between the two stones.
You are given the coordinates of Freddy’s stone, Fiona’s stone and all other stones in the lake. Your job is
- to compute the frog distance between Freddy’s and Fiona’s stone.
链接:lg1491
- 每次有大的活动,大家都要在一起“聚一聚”,不管是去好乐迪,还是避风塘,或者汤姆熊,大家都要玩的痛快。还记得心语和花儿在跳舞
- 机上的激情与释放,还记得草草的投篮技艺是如此的高超,还记得狗狗的枪法永远是’S’……还有不能忘了,胖子的歌声永远是让我们惊叫
- 的!!
- 今天是野猫的生日,所以想到这些也正常,只是因为是上学日,没法一起去玩了。但回忆一下那时的甜蜜总是一种幸福嘛。。。
- 但是每次集合的时候都会出现问题!野猫是公认的“路盲”,野猫自己心里也很清楚,每次都提前出门,但还是经常迟到,这点让大家很是
- 无奈。后来,野猫在每次出门前,都会向花儿咨询一下路径,根据已知的路径中,总算能按时到了。
- 现在提出这样的一个问题:给出n个点的坐标,其中第一个为野猫的出发位置,最后一个为大家的集合位置,并给出哪些位置点是相连
- 的。野猫从出发点到达集合点,总会挑一条最近的路走,如果野猫没找到最近的路,他就会走第二近的路。请帮野猫求一下这条第二最短
- 路径长度。
链接:lg1119
- B地区在地震过后,所有村庄都造成了一定的损毁,而这场地震却没对公路造成什么影响。但是在村庄重建好之前,所有与未重建完成的村
- 庄的公路均无法通车。换句话说,只有连接着两个重建完成的村庄的公路才能通车,只能到达重建完成的村庄。
- 给出B地区的村庄数N,村庄编号从0到N-1,和所有M条公路的长度,公路是双向的。并给出第i个村庄重建完成的时间t[i],你可以认为
- 是同时开始重建并在第t[i]天重建完成,并且在当天即可通车。若t[i]为0则说明地震未对此地区造成损坏,一开始就可以通车。之后有
- Q个询问(x, y, t),对于每个询问你要回答在第t天,从村庄x到村庄y的最短路径长度为多少。如果无法找到从x村庄到y村庄的路径,经
- 过若干个已重建完成的村庄,或者村庄x或村庄y在第t天仍未重建完成 ,则需要返回-1。