Preparing NOJ

水獭看动漫

1000ms 65536K

Description:

水獭发现为了看更多的集数,几乎每部作品都不能完整的看完,这让她心痒难耐~~于是她与他重新商议,希望能把想看的动漫全部看完,想到他当然不会同意这么“朴素而暴力”的新方案,她提出了“优化”条件――在看完某些前传或者是排序靠前的几集后,后面的内容可以跳着看(因为内容的关联所以可以直接跳过一些部分以缩短时间)。
假定,直接看某集A和某集B需用时Ca和Cb,但是在看完A后再看B的话,可以缩短时间为Db(保证Db≤Cb),从而总时间缩短了。但是,先看B后看A的话,不能缩短时间。
现在,给出若干这种联系,请计算出看完所有动漫所需要的最短时间。

Input:

第一行包含一个正整数Q,表示测试数据组数(1≤Q≤10);
每组测试数据包含若干行:
第一行仅有一个正整数N(1≤N≤100),表示有N集动漫;第二行包含N个正整数Ci,表示在没有“前情提要”时,看完第i集需要的时间;
第三行包含一个正整数M(M≤5000),表示有M个剧情的联系(可以缩短时间);接下来M行,每行三个正整数A,B,D,表示,在已看完A的情况下看B所需时间缩短为D。
为简化数据,假定所有剧集从1至N连续编号,A和B皆为有效编号,D一定不大于对应该集的C(1≤C,D≤10000),且不存在环!!!

Output:

每组数据对应一行输出,仅包含一个正整数,表示看完所有动漫所需最小时间。

Sample Input:

1
3
4 2 5
1
1 2 1

Sample Output:

10

Note:

本题由旧版NOJ导入,来源:7B

Info

NOJ

Provider NOJ

Code NOJ2001

Tags

Submitted 1

Passed 1

AC Rate 100%

Date 04/20/2019 10:03:10

Related

Nothing Yet