#P15056. [2026省选联测]通行卡

    ID: 14272 传统题 1000ms 256MiB 尝试: 2 已通过: 1 难度: 8 上传者: 标签>图论动态规划CF2400最短路搜索状压DP

[2026省选联测]通行卡

通行卡

题目描述

给定一个 nn 个点、mm 条边的有向图,点的编号从 11 到 nn。有 nn 张通行卡,编号从 11 到 nn,购买卡 ii 需要费用 aia_i。若要经过某个站点 ii,则必须购买通行卡 ii;若已购买该站点的通行卡,则可以在行程中任意多次经过该站点。

你需要从点 11 到点 nn 再回到点 11,求这一往返行程所需购买通行卡的最小总费用。若不存在从点 11 到点 nn 再回到点 11 的路线,输出 −1-1。

输入格式

每个测试文件均包含多组测试数据。

第一行输入一个正整数 TT,表示测试数据的组数。

接下来每组测试数据:

  • 第一行两个整数 n,mn,m。
  • 第二行 nn 个正整数 各卡的费用 a1,a2,…,ana_1,a_2,\ldots,a_n。
  • 接下来 mm 行,每行两个正整数 ui,viu_i,v_i,表示从 uiu_i 到 viv_i 的一条边。

输出格式

对于每组测试数据,输出一个整数,表示答案。

样例输入

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