Skip to content

1051: 日天卖面包

题目

题目描述

日天想要开一家面包店,卖各种各样的面包,他决定把店开在 $n$ 个城市中的 1 个,这些城市的编号从 1 到 $n$。而这些城市之间有 $m$ 条道路,每一条连接着两个城市。

为了能在面包店里烤面包,日天需要一些制造面包的原料,而这些原料只在一些城市里有。k个原料城市分别在 $a_1,a_2,\cdots,a_k$, 且 $a_i\in [1,n]$

然而不幸的是,当地有一个政策,面包店不能开在有原料的城市里,因此他只能将面包店开在另外的 $n-k$ 个城市中。当然,原料是要有运输费用的,日天需要为每 1 道路长度支付 1 元。

更严谨的说,如果日天吧面包店开在某一个城市 $b$ ($a_i\neq b,\forall 1\leq i\leq k$) , 并选择了一个有原料的城市 $s$ ( $s=a_j, 1\leq j\leq k$ ),并且 $b$ 和 $s$ 被一些路径连接在一起,这些路径的长度之和为 $x$ (如果有多条路径,日天可以选择他想要的那一条路径),则日天需要支付 $x$ 元。

日天想要让自己的面包店成本最低,所以需要最低的运费。

输入格式

第一行,有三个整数 $n, m, k$,分别对应城市数,道路数和有原料城市的数量。

接下来的 $m$ 行,每一行包含三个整数 $u, v, l$ ( $u\neq v$ ),表示城市 $u$ 和 $v$ 之间有一条长度为 l 的道路。

如果 $k > 0$,那么最后一行会有 $k$ 个不同的整数 $a_1, a_2, \cdots, a_k$ ,表示各个有原料城市的编号。如果 $k = 0$,这一行不会出现。

输出格式

输出日天需要支付的最少的运费。

如果不存在能够开面包店的城市,则输出 -1

样例输入

样例输入1

text 5 4 2 1 2 5 1 2 3 2 3 4 1 4 10 1 5

样例输入2

text 3 1 1 1 2 3 3

样例输出

样例输出1

text 3

样例输出2

text -1

数据范围

对于50%的数据, $1\leq n \leq 20$

对于100%的数据, $1\leq n, m \leq 1e5$

其中 $1\leq k \leq n, 1\leq l\leq 1e9$

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!