编程介的小学生 2019-12-31 18:01 采纳率: 20.5%
浏览 68

Sisters 的实现方法

Problem Description
Mikoto(Railgun) is an excellent ESP(Extra Sensory Perception) girl with the dreadful skill Railgun in Academy City.

But there is a bitter reality that Mikoto's sisters are being massacred by Yuriko(Accelerator) for experiments.

As Yuriko is the most powerful ESPer, what Mikoto can do is to destroy all related laboratories in Academy City to delay the massacre.

N Laboratories are connected by M wires and the power system can be considered to an undirected graph.

Academy City is divided into several districts.

If there are at least two non-intersecting paths between two laboratories, then the two cities belong to the same district.

Two paths are considered as non-intersecting paths if and only if there is no same edge in both of them.

If there are one wire connecting two laboratories of two different districts, then the two districts are neighbors. Power can be transported between neighbor districts.

Mikoto can destroy all laboratories in the district where she is by the Railgun, that costs K+X(X is the numbers of laboratories in this district) points energy. Mikoto can use the Railgun anywhere and any number of times.

What's more, Mikoto generates electricity at the same time she shoot the Railgun. Mikoto can use the power to destroy all laboratories in other districts via wires. For any district to be attacked by electricity, the cost is f(n) points energy, and n is the number of districts (excluding the district where Mikoto shoot the Railgun) in the path from Mikoto to it. More specifically, if Mikoto have shot the Railgun destroying all laboratories in the district she chose, she can choose several other districts to be attacked by electricity she generate and the cost for each district is described above.

Now, the problem is the mininum cost to destroy all laboratories.

Input
There are several test cases.

For each test case, the first line contains three integers, N(1 ≤ N ≤ 1000), M(1 ≤ M ≤ 1000000), K(1 ≤ K ≤ 1000000000).
Then, 2 to M + 1 lines, each line contain two different integers a and b (1 ≤ a,b ≤ N), meaning that there is a undirected wire between laboratories a and b.

Then, the M + 2 lines contain N-1 number, meaning f(1), f(2), ... , f(n - 1). (0 ≤ f(1) ≤ f(2) ≤ ... ≤ f(N - 1) ≤ 1000000000)

You can safely assume that all numbers in the input and output will in the range of 32-bit signed integer and all the laboratories are connected by wires.

Input is terminated by EOF.

Output
For each test case, output one single number which is the mininum cost to destroy all laboratories.

Sample Input
5 5 10
1 2
1 3
2 3
1 4
2 5
5 10 15 20
5 4 10
2 1
3 2
4 1
5 3
4 9 11 12

Sample Output
23
34

  • 写回答

0条回答 默认 最新

    报告相同问题?

    悬赏问题

    • ¥15 【提问】基于Invest的水源涵养
    • ¥20 微信网友居然可以通过vx号找到我绑的手机号
    • ¥15 寻一个支付宝扫码远程授权登录的软件助手app
    • ¥15 解riccati方程组
    • ¥15 display:none;样式在嵌套结构中的已设置了display样式的元素上不起作用?
    • ¥15 使用rabbitMQ 消息队列作为url源进行多线程爬取时,总有几个url没有处理的问题。
    • ¥15 Ubuntu在安装序列比对软件STAR时出现报错如何解决
    • ¥50 树莓派安卓APK系统签名
    • ¥65 汇编语言除法溢出问题
    • ¥15 Visual Studio问题