F.A.Qs | Home | ProblemSet | Status | Ranklist | Contest | Login | Register | 捐赠本站 |
---|
你的程序必须从标准输入读入。第一行包含三个由空格隔开的整数N,M和K。接下来的 M行描述最开始的M 条道路。这M行中的第i行包含由空格隔开的整数ai,bi和c i,表示有一条在a i和b i之间,费用为c i的双向道路。接下来的K行描述新建的K条道路。这 K行中的第i行包含由空格隔开的整数 xi和yi,表示有一条连接城镇xi和yi新道路。最后一行包含N个由空格隔开的整数,其中的第j个为pj,表示从城镇j 前往城镇 1的人数。
输入也满足以下约束条件。
1 ≤ N ≤ 100000;
1 ≤ K ≤ 20;
1 ≤ M ≤ 300000;
对每个i和j,1 ≤ ci, pj ≤ 10^6;
你的程序必须输出恰好一个整数到标准输出,表示能获得的最大的收入。