#P3380. [Usaco2004 Open]Cave Cows 1 洞穴里的牛之一

    ID: 2570 传统题 1000ms 512MiB 尝试: 109 已通过: 51 难度: 4 上传者: 标签>难度分类普及+/提高-枚举与搜索广度优先搜索图论状态扩展图状态编码状态去重位运算位计数CF1600Orange

[Usaco2004 Open]Cave Cows 1 洞穴里的牛之一

[USACO 2004 Open] Cave Cows 1 洞穴里的牛之一

题目描述

贝茜在一座洞穴中探险。洞穴有 NN 个洞室,编号为 11 到 NN,其中 11 号是入口。洞室之间有 MM 条双向通道;每条通道连接两个不同的洞室,同一对洞室之间最多有一条通道。

有 KK 个不同的洞室各放着一捆干草。贝茜的体重指数起初为 00,每吃一捆干草就增加 11。只有当体重指数不超过一条通道的宽度时,她才能通过该通道。经过有干草的洞室时,她可以选择先不吃。

贝茜从 11 号洞室出发,最后也必须从 11 号洞室离开。她最多能吃多少捆干草?

输入格式

从标准输入读入。第一行是三个整数 N,M,KN,M,K。接下来 KK 行各给出一个放有干草的洞室编号。随后 MM 行每行三个整数 u,v,wu,v,w,表示洞室 u,vu,v 之间的通道宽度为 ww。

输出格式

向标准输出输出一行一个整数,表示最多吃到的干草捆数。

6 7 5
1
2
3
4
5
1 2 3
3 6 2
6 2 10
2 4 1
5 1 1
4 5 1
1 6 1
4

样例解释

直接通往入口的通道最宽为 33,所以回到入口之前最多能吃 33 捆。贝茜可沿 1,5,4,2,6,3,6,2,11,5,4,2,6,3,6,2,1 行进,在 5,3,25,3,2 号洞室各吃一捆,最后在入口再吃一捆。

数据范围与约定

1≤N≤1001\le N\le100,1≤M≤1 0001\le M\le1\,000,1≤K≤141\le K\le14,1≤u,v≤N1\le u,v\le N,1≤w≤1001\le w\le100。