Problem 4131 --建造堡垒

4131: 建造堡垒

"
Time Limit $1$ 秒/Second(s) Memory Limit $512$ 兆字节/Megabyte(s)
提交总数 $1$ 正确数量 $1$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签


AMC想建立一个中央城镇,他发现不够木材。所以他要采集更多的木材,他让苦逼的农民去IPC收集


AMC已经建好了很多个锯木厂,周围有一片很大的森林,锯木厂之间连接着双向道路(锯木厂可以它自身连接),每当IPC走过一条路,他会收集到10个木材。


现在AMC需要K个木材,所以苦逼的IPC必须至少收集K个木材以上。


这些锯木厂被从1到N标记着编号,IPC从S锯木厂开始,当他完成他的工作,AMC又给他另外一个工作:到达锯木厂T建造一个中央城镇,icpc必须设计好他的路线,因为ACM要尽快地建好中央城镇


现在IPC请你帮忙,计算出他完成工作最小的时间(包括收集木材和建立城镇),如果不可能完成,输出 -1。



第一行有两个整数N (1<=N<=5000), M (0<=M<=100000)代表锯木厂的个数和路径的条数。


接下来的M行每行有三个整数A B C (1<=A, B<=N; 1<=C<=100),表示存在一条路径连接着A锯木厂和B锯木厂,经过这一条路需要花费C时间。锯木厂被从1到N标记着编号。


最后一行有三个整数S T K (1<=S, T<=N; 0<=K<=500),是问题描述中提及到的。S T K。



每行输出每个案例的答案


4 4
1 2 1
2 3 2
1 3 100
3 4 1
1 3 50
7

推荐代码 查看4131 所有题解 上传题解视频得图灵币

本题记录 用 户(点击查看用户) 运行号(点击购买题解) 时 间
算法最快[$4 $ms] AOJ大管家 1097328 2024-04-22 14:43:40
内存最少[$5872 $KB] AOJ大管家 1097328 2024-04-22 14:43:40
第一AC AOJ大管家 1097328 2024-04-22 14:43:40
第一挑战 AOJ大管家 1097328 2024-04-22 14:43:40

赛题来源/所属竞赛 N/A

竞赛编号 竞赛名称 竞赛时间 访问比赛