P5096 [USACO04OPEN] Cave Cows 1

Few people know that cows actually really like exploring caves. There are $N$ ( $1 \leq N \leq 100$ ) chambers in the cave, connected by $M$ ( $1 \leq M \leq 1000$ ) bidirectional passages. Between any pair of chambers, there is at most one bidirectional passage. There are $K$ ( $1 \leq K \leq 14$ ) chambers, each containing one bale of hay. Every time a cow eats one bale of hay, her weight index increases by $1$. The greedy Bessie wants to explore the cave and hopes to eat as much hay as possible, but each passage has a width threshold: if her weight index exceeds the corresponding threshold, Bessie will get stuck. She starts from chamber $1$ with weight index $0$. After wandering around in the cave, she must return to chamber $1$. What is the maximum number of hay bales she can eat? Note that when Bessie passes through a chamber, she does not have to eat the hay in it.

The first line contains $N, M, K$. The next $K$ lines each contain one integer, indicating a chamber that contains one bale of hay. Then the next $M$ lines each contain three integers, indicating the two endpoints of a bidirectional passage and its width threshold.

The maximum number of hay bales that can be eaten.

Translated by ChatGPT 5