P5096 [USACO04OPEN] Cave Cows 1

题目描述

很少人知道其实奶牛非常喜欢到洞穴里面去探险。

洞窟里有 $N ( 1 \leq N \leq 100 )$ 个洞室，由 $M ( 1 \leq M \leq 1000 )$ 条双向通道连接着它们。每对洞室间至多只有一条双向通道，有 $K ( 1 \leq K \leq 14 )$ 个洞室，里面放有 $1$ 捆干草．牛吃 $1$ 捆干草，体重指数就会增加 $1$。

贪吃的贝茜要到洞窟里面探险，她希望能吃尽量多的干草，但每条通道有一个宽度阈值，如果体重指数超过相应的阈值，贝茜就会被卡住。

她从洞窟 $1$ 出发，体重指数为 $0$。在洞里溜达一圈后，她要返回洞窟 $1$。

那她最多能吃多少捆干草呢？注意，贝茜经过一个洞室，不一定非要吃掉里面的干草。

输入格式

第 $1$ 行输入 $N,M,K$。

之后 $K$ 行每行一个整数，表示在这个洞室放有一捆干草；接下来 $M$ 行每行三个整数，表示一条双向通道的起点终点和宽度阈值。

输出格式

最多能吃掉的干草数。

输入输出样例 #1

输入 #1

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

输出 #1

4