P11225 [COTS 2019] 疏散 Sklonište

译自 [Izborne Pripreme 2019 (Croatian IOI/CEOI Team Selection)](https://hsin.hr/pripreme2019/) D2T2。$\texttt{4s,0.5G}$。

给定 $N$ 个点 $M$ 条边的无向连通图，边有边权。有 $K$ 个关键点 $A_1,A_2,\cdots,A_K$，**容量**为 $S_1,S_2,\cdots,S_K$。 图中的居民要疏散。也就是说，你需要构造一个序列 $B_1,B_2,\cdots,B_N$，使得： - $\forall 1\le i\le N$，$1\le B_i\le K$； - 对于 $1\le i\le K$，定义 $\displaystyle \mathrm{cnt}_i=\sum_{1\le j\le N} [B_j=i]$，也就是 $i$ 在 $B$ 序列中出现的次数。则 $\mathrm{cnt}_i\le S_i$。 定义序列 $B$ 的**疏散时间**为 $\displaystyle \max_{1\le i\le N} \operatorname{dist}(i,A_{B_i})$，其中 $\operatorname{dist}(u,v)$ 指图中 $u,v$ 间最短路的长度。 求出疏散时间的最小值。保证 $\sum_i S_i\ge N$。

第一行，三个正整数 $N,M,K$； 接下来 $M$ 行，每行三个正整数 $u,v,w$，描述一条无向边 $(u,v)$，边权为 $w$。保证 $u\neq v$。 接下来 $K$ 行，每行两个正整数描述 $A_i,S_i$。 保证 $\sum_i S_i\ge N$。

输出一行一个数，表示答案。

对于 $100\%$ 的数据，保证： - $1\le N\le 10^5$； - $N-1\le M\le 3\times 10^5$； - $1\le K\le 17$； - 给定图连通，无自环； - $1\le w,S_i\le 10^9$； - $1\le u,v,A_i\le N$； - $S_i$ 两两不同； - $\sum_i S_i\ge N$。 | 子任务编号 | $N\le $ | $M\le $ | $K\le$ | 得分 | | :--: | :--: |:--: | :--: | :--: | | $ 1 $ | $ 100 $ | $ 500 $ | $5$ | $30$ | | $ 2 $ | $ 10^5 $ | $ 3\times 10^5 $ | $10 $ | $30$ | | $ 3 $ | $ 10^5 $ | $ 3\times 10^5 $ | $17$ | $40$ |