P13749 [NWERC 2024] Kruidnoten

每周，Karlijn 和她的队友们都会参加他们大学的竞赛编程训练。 长时间的思考和编程让人非常疲惫，他们需要大量的零食来支撑训练。 他们已经将带零食的任务分配得井井有条：其他两个人分别带 stroopwafels 和盐棒，而 Karlijn 的任务是提供 kruidnoten。 :::align{center}  Kruidnoten，一种典型的荷兰零食。图片由 Hanno Lans 在 [Wikimedia Commons](https://commons.wikimedia.org/w/index.php?curid=64873895) 发布，采用 CC BY 4.0 协议。 ::: 她通常会在从家去大学的路上顺便买 kruidnoten。 她家所在小镇的自行车道网络由若干个路口组成，这些路口通过不同长度的自行车道相连。 路口编号为 $1$ 到 $n$。 Karlijn 的家在 $1$ 号路口，大学在 $n$ 号路口。 有多家商店出售 kruidnoten，但有些商店经常断货。 Karlijn 想尽快到达大学，因此她习惯在出门前在线查询哪些商店还有 kruidnoten。 根据这些信息，她会选择经过某家有货商店的最短路径。 图 K.1 展示了一个例子。 :::align{center}  图 K.1：来自样例输入 1 的一种可能情况，并非所有商店都有 kruidnoten。在这种情况下，Karlijn 在 $3$ 号路口的商店购买 kruidnoten，最短路径长度为 $11$。 ::: 现在，她想知道通常应该为去训练预留多少时间。 根据长期经验，Karlijn 知道每家商店有多大概率还没有卖完 kruidnoten。 特别地，她观察到每家商店的 kruidnoten 库存情况是相互独立的。 如果她想在路上经过某家有货的商店，从家到大学的最短路径的期望长度是多少？

输入包括： - 一行三个整数 $n$、$m$ 和 $k$（$2\leq n\leq 2 \cdot 10^5$，$1\leq m\leq 2 \cdot 10^5$，$1\leq k\leq n$），分别表示路口数、自行车道数和可能出售 kruidnoten 的商店数。 - 接下来 $m$ 行，每行三个整数 $i$、$j$ 和 $\ell$（$1\leq i, j\leq n$，$i \neq j$，$1 \leq \ell \leq 10^6$），表示 $i$ 号和 $j$ 号路口之间有一条长度为 $\ell$ 的自行车道。 保证每对路口之间至多有一条自行车道。 此外，保证任意两个路口之间都可以骑车到达。 - 接下来 $k$ 行，每行一个整数 $i$（$1\leq i \leq n$）和一个浮点数 $p$（$0 < p \leq 1$，小数点后最多四位），表示在 $i$ 号路口有一家商店，该商店还有 kruidnoten 的概率为 $p$。 保证每个路口至多有一家 kruidnoten 商店。

如果 Karlijn 在路上无法买到 kruidnoten 的概率大于 $0$，输出“impossible”。 否则，输出她在路上买到 kruidnoten 时，从家到大学的最短路径的期望长度。 你的答案的绝对误差或相对误差不超过 $10^{-6}$。

由 ChatGPT 4.1 翻译