首页 > ACM题库 > HDU-杭电 > hdu 3383 Navi Navigation待解决[解题报告]C++
2014
03-22

hdu 3383 Navi Navigation待解决[解题报告]C++

Navi Navigation

问题描述 :

The Navi villages on Pandora are part of gigantic hometrees. Hometrees specialize in producing different types of fruits that Navi like to eat. Neytiri’s mother Mo’at asks her to calculate the shortest path between two given hometrees that allows Mo’at to collect every different type of fruit exactly once. Your goal is to help Neytiri calculate these paths. Warning: since there are many hometrees on Pandora, you will not be able to simply examine all possible paths and select the least expensive.

输入:

Paths between hometrees are described beginning with the line “GRAPH BEGIN”. Additional lines lists individual hometrees (nodes), the type of fruit produced by the hometree, the distance to the neighboring hometrees, followed (on the same line) by their neighboring hometrees (edges). The line “GRAPH END” ends the list of connection descriptions. The next lines describe pairs of hometrees for which answers need to be calculated, each on a single line. Following these lines, a completely new instance of the problem can be given, starting from scratch.

You may assume any hometree can reach any other hometree by some path. Each hometree will be listed at least once as the first item on some line between the GRAPH BEGIN and GRAPH END. The same hometree can be listed more than once with different distance values, but it must always have the same type of fruit assigned to it. Individual connections can appear at most once. It is valid to list only a hometree and its color (specifying no new connections).

Fruit names will be integers. Not all integers have to be used, however. Your path need only try to collect fruits that at least one tree grows.

输出:

Paths between hometrees are described beginning with the line “GRAPH BEGIN”. Additional lines lists individual hometrees (nodes), the type of fruit produced by the hometree, the distance to the neighboring hometrees, followed (on the same line) by their neighboring hometrees (edges). The line “GRAPH END” ends the list of connection descriptions. The next lines describe pairs of hometrees for which answers need to be calculated, each on a single line. Following these lines, a completely new instance of the problem can be given, starting from scratch.

You may assume any hometree can reach any other hometree by some path. Each hometree will be listed at least once as the first item on some line between the GRAPH BEGIN and GRAPH END. The same hometree can be listed more than once with different distance values, but it must always have the same type of fruit assigned to it. Individual connections can appear at most once. It is valid to list only a hometree and its color (specifying no new connections).

Fruit names will be integers. Not all integers have to be used, however. Your path need only try to collect fruits that at least one tree grows.

样例输入:

GRAPH BEGIN 
a 3 1 b e 
b 2 2 c 
c 1 1 d
d 5
e 2
GRAPH END
a d
a c
GRAPH BEGIN
e 1 2 f
e 1 3 g
f 2
g 2
h 3 4 g f
GRAPH END
h e

样例输出:

a d 4.0
a c NONE
h e 6.0


  1. 可以参考算法导论中的时间戳。就是结束访问时间,最后结束的顶点肯定是入度为0的顶点,因为DFS要回溯

  2. 题目需要求解的是最小值,而且没有考虑可能存在环,比如
    0 0 0 0 0
    1 1 1 1 0
    1 0 0 0 0
    1 0 1 0 1
    1 0 0 0 0
    会陷入死循环

  3. 为什么for循环找到的i一定是素数叻,而且约数定理说的是n=p1^a1*p2^a2*p3^a3*…*pk^ak,而你每次取余都用的是原来的m,也就是n