shunfurh
编程介的小学生
2018-11-22 08:35
采纳率: 92.7%
浏览 333

这个问题解决的思路是什么,是不是需要遍历才能解决?

Problem Description
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
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.

Output
For each input case ,output a line containing a single number, which is the minimum time it need to visit all the streets.

Sample Input
3 3
1 2 4
4 1 3
1 2
2 3
3 1
0 0

Sample Output
7

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 邀请回答

1条回答 默认 最新

相关推荐