首页 > ACM题库 > HDU-杭电 > hdu 3606 The police caught the thief待解决[解题报告]C++
2014
11-27

hdu 3606 The police caught the thief待解决[解题报告]C++

The police caught the thief

问题描述 :

In a country, a thief stole the king’s jewels, the king was very angry, asked the police to seize he as soon as possible,the thief was afraid of stealing king’s jewels, to prevent the police from seizing , he decided to randomly walk in the nearby cities or stay put a day, the police found the thief at “t” City and himself at “s” city, and received information (police can always know where is the thief ). he decided to quickly caughting the thief.The police want to know about how long to seize the thief in the worst situation. This country can be seen as a undirected graph, there are N cities, M edges .As we know the police are very smart and quick; a day he will go to a closer city to the thief, if there are several cities, he will choose the smallest label city, if the thief is not in that city he will continue to go to the next one closer city to the thief . If they have several cities, they will select the smallest label city too, in other word ,a day police can move two steps. Suppose the police move first, please tell the police how many days to seize the thief in worst situation.

输入:

Multi test cases;  
The first line consist of the two integers N, M (1 ≤ N, M ≤ 1000), separated by spaces; The second line consist of two integers is s, t, respectively, the initial city where the police and thieve The third line to the M +1 line input two integers a and b ,there is one edge between city a and b.,
Processing to the end of the file;

输出:

Multi test cases;  
The first line consist of the two integers N, M (1 ≤ N, M ≤ 1000), separated by spaces; The second line consist of two integers is s, t, respectively, the initial city where the police and thieve The third line to the M +1 line input two integers a and b ,there is one edge between city a and b.,
Processing to the end of the file;

样例输入:

4 3 
1 4 
1 2 
2 3 
3 4 
9 9 
9 3 
1 2 
2 3 
3 4 
4 5 
3 6 
4 6 
4 7 
7 8 
8 9 

样例输出:

2
3


  1. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。