#P15056. [2026省选联测]通行卡
[2026省选联测]通行卡
通行卡
题目描述
给定一个 个点、 条边的有向图,点的编号从 到 。有 张通行卡,编号从 到 ,购买卡 需要费用 。若要经过某个站点 ,则必须购买通行卡 ;若已购买该站点的通行卡,则可以在行程中任意多次经过该站点。
你需要从点 到点 再回到点 ,求这一往返行程所需购买通行卡的最小总费用。若不存在从点 到点 再回到点 的路线,输出 。
输入格式
每个测试文件均包含多组测试数据。
第一行输入一个正整数 ,表示测试数据的组数。
接下来每组测试数据:
- 第一行两个整数 。
- 第二行 个正整数 各卡的费用 。
- 接下来 行,每行两个正整数 ,表示从 到 的一条边。
输出格式
对于每组测试数据,输出一个整数,表示答案。
样例输入
5
7 0
7 4 8 10 1 7 1
7 5
2 3 3 4 7 3 3
7 2
1 2
2 1
2 3
3 7
7 7
5 3 6 3 3 5 3
6 5
1 5
5 6
6 2
2 7
5 1
7 6
7 2
4 10 2 9 5 6 9
1 7
7 1
7 9
1 1 3 3 1 1 1
1 4
4 7
3 1
7 3
1 2
6 7
5 1
7 5
2 6
样例输出
-1
11
19
13
5