2020新生赛报名网站,请先注册登录xdoj以后再通过下方网站报名 http://acm.xidian.edu.cn/signuppage.php

问题 1481. -- 运送货物

1481: 运送货物

时间限制: 1 Sec  内存限制: 128 MB
提交: 341  解决: 57
[提交][状态][讨论版]

题目描述

 比赛试题压缩包:

http://acm.xidian.edu.cn/download/2020-xidian-campus-online.zip

解压密码见首页~~

注意:题面中 “他想请你求出这所有货物花费总和的最小值” 改为 “他希望最小化每批货物的花费“。

容易证明,“所有货物花费总和的最小” 和 ”每批货物的花费最小“ 是等价的。

注意:题面中 “假设 a 城市和 b 城市之间有通道,那么理论上会花费一定的比特币”  改为  “假设一批货物经过了 a 城市到 b 城市的通道,那么该批货物会花费一定的比特币作为通行费”

注意:如果存在一条路径 (可以经过任意条道路) 从 a 城市出发,到 b 城市结束,称 a 可到达 b。如果 a 可到达 b,且 b 可到达 a,称 a 和 b 可以互相到达。

输入

输出

提示

来源

[提交][状态][讨论版]