Public Judge

pjudge

Time Limit: 1 s Memory Limit: 1024 MB Total points: 100 Hackable ✓

# 21662. 【PR #7】道路重建

统计

在一个遥远的国家里有 $l$ 个城市,编号为 $0,1,\cdots,l-1$,围着一个大湖建成一圈。城市内和城市间有很多交通线路,并且它们都是双向的。

每个城市里都有 $n$ 个火车站,编号为 $0,1,\cdots,n-1$,由 $m$ 条动车线路相连。由于这些城市是一起修建的,所以任意两个城市内的火车站连接情况完全一致,即点集和边集都相等。

有些火车站是枢纽站。如果火车站 $s$ 在某个城市是枢纽站,那么所有城市的 $s$ 号火车站都是枢纽站。相邻城市的编号相同的枢纽站会被高铁线路连接。

一场天灾之后,所有这些线路都需要重建才可以被投入使用。由于城市之间非常相似,重建的费用也很有规律,具体如下:

  • 每个城市 $i$ 都有两个正整数 $a_i,b_i$ 。
  • 每条动车线路都有一个正整数 $d_j$ ,不同城市的同一条动车线路的 $d_j$ 相等。
  • $i$ 号城市的 $j$ 号动车线路的重建费用是 $b_i+d_j$ 。
  • $i$ 号城市和 $(i+1)\bmod l$ 号城市之间的任意一条高铁线路的重建费用都是 $a_i$ 。

你需要花费尽可能少的代价,重建若干条线路,使得国家里的任意两个火车站可以互达。

输入格式

第一行两个正整数 $n,m$ 。

接下来 $m$ 行,每行三个整数 $u_j,v_j,d_j$ ,描述一条连接 $u_j$ 和 $v_j$ 的动车线路。

接下来一行一个正整数 $l$ 。

接下来 $l$ 行,每行两个正整数 $a_i,b_i$ ,描述一个城市。

接下来一行一个正整数 $r$ ,表示一个城市里枢纽站的个数。

最后 $r$ 行,每行一个非负整数 $s_k$ ,表示每个城市的 $s_k$ 号火车站是枢纽站。

输出格式

一行一个正整数,表示使得所有火车站两两互达的最小代价。

样例一

input

2 1
0 1 3
3
6 1
4 2
5 3
1
1

output

24

样例二

input

3 3
0 1 7
1 2 8
2 0 5
4
8 1
5 1
9 3
7 3
2
1
2

output

76

样例三、四

见下发文件。

数据范围与提示

对于所有数据,$2\le n\le 10^4, 1\le m\le 10^5, 0\le u_i,v_i,s_k<n, 1\le d_j,a_i,b_i\le 10^9, 3\le l\le 10^5, 1\le r\le n$ ,图中无重边自环且连通,$s_k$ 两两不同。

子任务编号 特殊限制 分值
$1$ $n,l\le 10^3$ $20$
$2$ $a$ 里不同的值的个数不超过 $20$ $20$
$3$ $b$ 里不同的值的个数不超过 $20$ $20$
$4$ $r\le 500$ $20$
$5$ $ $ $20$

时间限制:$\texttt{1s}$

空间限制:$\texttt{1024MB}$