给你一个无向图,n 个城市,m 条道路,每个城市有一个人口数量 pi,每条边有一个花费 wi 元。
现在给你下达一个任务:给你 k 元资金,选择一些道路修建,使得能到达首都的人口数最多。
其中首都是固定的 1 号结点。
第一行一个整数 T,表示有 T 组数据。 每组数据的第一行有三个整数 n,m,k,分别表示城市数量,道路数量,修建道路的资金。 每组数据的第二行有 n 个数,第 i 个数 pi 表示第 i 座城市的人口数量。 接下来 m 行,每行三个值 ui,vi,wi ,分别表示一条道路的两个端点及修建道路的花费。
对于每组数据输出一个整数,表示最多可使多少人口能够到达首都。
对于 100% 的数据满足:
1≤T≤20,4≤n≤16,1≤m≤100,1≤k≤100000,1≤pi≤10000,1≤u,v≤n,1≤c≤1000。
## 题目描述:
给你一个无向图,$n$ 个城市,$m$ 条道路,每个城市有一个人口数量 $p_i$,每条边有一个花费 $w_i$ 元。
现在给你下达一个任务:给你 $k$ 元资金,选择一些道路修建,使得**能到达首都的人口数**最多。
其中首都是固定的 $1$ 号结点。
## 输入格式:
第一行一个整数 $T$,表示有 $T$ 组数据。
每组数据的第一行有三个整数 $n,m,k$,分别表示城市数量,道路数量,修建道路的资金。
每组数据的第二行有 $n$ 个数,第 $i$ 个数 $p_i$ 表示第 $i$ 座城市的人口数量。
接下来 $m$ 行,每行三个值 $u_i,v_i,w_i$ ,分别表示一条道路的两个端点及修建道路的花费。
## 输出格式:
对于每组数据输出一个整数,表示最多可使多少人口能够到达首都。
## 数据范围
对于 $100\%$ 的数据满足:
$1 \le T \le 20$,$4 \le n \le 16$,$1 \le m \le 100$,$1 \le k \le 100000$,$1 \le p_i \le 10000$,$1 \le u,v \le n$,$1 \le c \le 1000$。