问题 1481. -- 运送货物

1481: 运送货物

时间限制:1000 ms 内存限制:128 MB
提交:359 解决:60
[ 提交][ 状态][ 讨论版]

题目描述

比赛试题压缩包:

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 可以互相到达。

输入

输出

提示

来源

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