问题1240--LiuGod上班

1240: LiuGod上班

[命题人 : ]
时间限制 : 3.000 sec  内存限制 : 128 MB

题目描述

题目背景

LiuGod暑假在杭州上班,很多在杭州上班的人都有同样的问题,那就是家和公司离得太远的。当然,LiuGod还可以选择住在附属酒店,这样就会离公司更近了;但是,附属酒店有时候会住满,此时就需要公司做一些决策。

题目描述

杭州可以看做由 \(n\) 个点组成的无向图,顶点从 \(1-n\) ,其中有 \(m\) 条无向边连接。在某些顶点上一共有 \(p\)  家公司和 \(r\) 个上班族,当然,每个上班族每天都需要从家里赶到公司。

为了帮助上班族,\(q\) 家附属酒店为他们提供房间。如果上班族住在酒店,那么他就可以从酒店去公司。同样的,酒店是有容量的,第 \(i\)  家酒店最多容纳的上班族为 \(h_i\)。

每个上班族会选择最短路径去上班,我们定义 \(d_i\) 为第 \(i\) 个上班族上班途中经过的路径总长,\(dmax=max\{d_i\}\) ,LiuGod希望合理的安排上班族与酒店的情况,使得 \(dmax\) 最小,这样无论如何他自己也能更快上班。

输入

第一行包含5个整数 \(n,m,p,q,r(1\leq n\leq m \leq 10^4,1\leq p,q\leq 100,1\leq r \leq 10^6)\)。

接下来 \(m\) 行,每行三个整数 \(u,v,w(1\leq u,v\leq n,1\leq w\leq 10^9)\) 表示顶点 \((u,v)\) 之间有一条长度为 \(w\) 的边。

接下来一行包含 \(p\) 个整数 \((x_1,x_2,\dots,x_p,1\leq x_i \leq n)\) , \(x_i\) 表示第 \(i\) 家公司所在顶点。

接下来 \(q\) 行每行两个整数 \((y_i,h_i,1\leq y_i \leq n,1\leq h_i\leq 10^6)\) ,表示第 \(i\) 家附属酒店所在顶点与可容纳人数。

接下来 \(r\) 行每行两个整数 \((s_i,k_i,1\leq s_i \leq n,1\leq k_i\leq p)\) ,表示第 \(i\) 个上班族所在顶点与公司编号。

输出

输出一个整数,表示最小的 \(dmax\) 值。 

样例输入 Copy

6 6 1 1 3
1 2 20
2 3 2
3 1 5
1 4 2 
2 5 10 
3 6 10
1
4 2
5 1
6 1
5 1

样例输出 Copy

15