| 题目名称 | 2091. [SYOI 2015] Asm.Def的打击序列 |
|---|---|
| 输入输出 | asm_lis.in/out |
| 难度等级 | ★★★ |
| 时间限制 | 4000 ms (4 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 10 |
| 题目来源 |
 cqw
于2015-11-04加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：15， 提交：74， 通过率：20.27% | ||||
 dydxh |
100 | 0.395 s | 1.27 MiB | C++ |
 wsp |
100 | 0.409 s | 3.94 MiB | C++ |
 feng |
100 | 0.431 s | 1.27 MiB | C++ |
 szzy |
100 | 0.753 s | 1.71 MiB | C++ |
 前鬼后鬼的守护 |
100 | 0.842 s | 39.46 MiB | C++ |
 cstdio |
100 | 0.854 s | 0.29 MiB | C++ |
 坐看321JG虐场 |
100 | 0.929 s | 0.57 MiB | C++ |
 葳棠殇 |
100 | 1.213 s | 1.83 MiB | C++ |
 Satoshi |
100 | 1.417 s | 0.33 MiB | C++ |
 ggwdwsbs |
100 | 1.500 s | 0.30 MiB | C++ |
| 本题关联比赛 | |||
| “Asm.Def战记之拉格朗日点”杯 | |||
| 关于 Asm.Def的打击序列 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
| ||||
|
| ||||
【题目描述】
白色圆柱形的“蓝翔”号在虚空中逐渐变大，一声沉闷的撞击后停住不动。空气阀开始“嘶嘶”作响。
Asm.Def钻出舱门，杜舰长热情地向他伸出右手，“来者可是Asm.Def？”
“正是。”他趁着握手将U盘递给舰长，“这里是所有目标位置，方教授说控制太空就靠你了，否则咱的通信卫星就是一坨废物。”
“没问题，就用这个，保证让它们灰飞烟灭。”杜舰长调出全息图像，是个细长的针状物体。
“阿姆斯特朗回旋加速喷气式阿姆斯特朗动能弹，”舰长介绍道，“本来想用强相互作用力材料，可惜没弄成，但撞击结构关键点，普通合金也够了。”
“雷达数据有误怎么办？靠信仰？”Asm.Def质疑。
“放心吧，我每个月都替它交党费。”
Asm.Def需要帮忙制定打击序列。我们可以把所有目标看做一个N个点，M条边的边带权有向图，每个点都是一个目标。
有两种手段：动能弹和激光。
Asm.Def可以发射若干枚（也可以是零枚）动能弹。每一枚动能弹会沿图中一条简单路径或简单环飞行：
简单路径形如p1->p2->…->pk，其中p1~pk互不相等，且(p1,p2)，(p2,p3)…(pk-1,pk)均为图中的有向边。这时目标p2,p3,…,pk会被摧毁，但p1未被摧毁（因为动能弹在p1处尚未充分加速）。
简单环形如p1->p2->…->pk->p1，其中p1~pk互不相等，且(p1,p2)，(p2,p3)…(pk,p1)均为图中的有向边。这时目标p1,p2,…,pk都会被摧毁。
一个目标至多出现在一枚动能弹的路径上（即所有动能弹的路径互不相交，包括简单路径中的p1），因为目标碎片十分危险。
动能弹的费用是它飞行路径的边权之和。
除了动能弹，也可以用激光摧毁一个目标，费用是C。
Asm.Def希望算出摧毁所有目标的最小费用。
【输入格式】
第1行3个整数：N,M,C。
接下来M行，每行3个整数s,t,v，代表有一条s->t的有向边，边权为v。
【输出格式】
1行1个整数，即摧毁所有目标的最小费用。
【样例输入1】
4 3 10 1 2 2 2 3 2 3 1 2
【样例输出1】
16
【样例输入2】
6 5 5 1 3 2 2 3 2 3 4 2 4 5 2 4 6 2
【样例输出2】
21
【提示】
样例1：一枚动能弹路径为1->2->3，花费6，用激光摧毁4，花费10.
样例2：一枚动能弹路径为1->3->4->5，花费6，用激光摧毁1,2,6，花费15.
对于40%的数据，2<=N<=5，1<=M<=10.
对于100%的数据，2<=N<=250，1<=M<=30000；s≠t；1<=s,t<=N；1<=v,c<=10000.
两对城市间可能有多条路径，但不会有自环。
【来源】
“Asm.Def战记之拉格朗日点”杯