首页 > ACM题库 > HDU-杭电 > hdu 2251 ShaDan’ Problem待解决[解题报告]C++
2014
01-04

hdu 2251 ShaDan’ Problem待解决[解题报告]C++

ShaDan’ Problem

问题描述 :

Long long ago , there is a person named ShaDan. He likes walking around the streets very much. He walks around the street until the sky is black every day. When he go back home , his mother always very angry with him. “what are you doing , it’ s so late now” his mother always asked him loudly. ShaDan always answer “I’m watching the scenery around the street”.
One day, when ShaDan was walking around the street, he thought how can I visit all the streets and cost minimum time. So that, he can go back home earlier and his mother will not blame him. The streets ShaDan visited is very strange. They are all one-way streets. All the cars on a street is drived along in one direction. But ShaDan can walk around the street in two directions. For example , if the street is from city i to city j , cars can only be drived on the street from the city I to city j. But ShaDan can walk around the street from the city i to city j and also can walk around the street form the city j to city i . In addition , ShaDan have a Super-capacity. Every move , he can choose a city i , and it doesn’t cost time. When he is in a city I,he have two ways to visit the streets.
The first one :he is in the city i , and he can walk around all the streets that from the city i ( for example i= 2 , he can walk 2->5, 2->3 , 2 – >6 ,if there exists a street ), it will costs he Wi to visit all the streets from city i.
The second one : he is in the city i, and he can walk around all the streets to city I ( for example i= 2 , he can walk 5->2, 4->2 , 3 – >2 ,if there exists a street ), it will costs he Pi to visit all the streets to city i.
Although ShaDan have a Super-capiacity , but his IQ is very low.
He is unable to deal with the problem . So he asked his best friends RPRUSH to help him to calculate the minimum time to visit all the streets.

输入:

Input contains multiple test cases. Each test case contains an integer N (1 <= N < = 300 , the number of city) and M (1 <= m <= 20000, the number of streets )in a line first line , the second line contain n integers( from W1 to Wn ). The third line contain n integers (from P1 to Pn). Then followed M line, each line contain two integers a and b , means there is a street from city a to city b.
If there are two or more streets from city a to b , it is also legal. The input ends with a line that has two non-positive numbers.

输出:

Input contains multiple test cases. Each test case contains an integer N (1 <= N < = 300 , the number of city) and M (1 <= m <= 20000, the number of streets )in a line first line , the second line contain n integers( from W1 to Wn ). The third line contain n integers (from P1 to Pn). Then followed M line, each line contain two integers a and b , means there is a street from city a to city b.
If there are two or more streets from city a to b , it is also legal. The input ends with a line that has two non-positive numbers.

样例输入:

3 3
1 2  4
4 1  3
1  2
2  3
3  1
0  0

样例输出:

7


  1. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术,也不懂什么是算法,从而也不要求程序员懂什么算法,做程序从来不考虑性能问题,只要页面能显示出来就是好程序,这是国内的现状,很无奈。

  2. L(X [0 .. M-1],Y [0 .. N-1])= 1 + L(X [0 .. M-2],Y [0 .. N-1])这个地方也也有笔误
    应改为L(X [0 .. M-1],Y [0 .. N-1])= 1 + L(X [0 .. M-2],Y [0 .. N-2])