令 $d_{i,j}$ 表示走到点 $i$ 且 $\sum_{i\in P}a_i=j$ 的最小的 $\sum_{i\in P}b_i$。直接跑 Dijkstra，算法运行途中每次对点 $i$ 上 $a$ 和为 $j$ 的更新必须保证 $a$ 和严格小于上一次访问，否则 $a$ 和与 $b$ 和均不小于上一次，不优，没有意义。
时间复杂度 $O((n+m)V\log ((n+m)V))$，因额外限制而常数极小，能过。
QOJ.ac
QOJ
As we are currently experiencing an overwhelming number of web requests for fetching user submissions, we have temporarily disabled the full submissions list. You must now be logged in to view submissions.
Discussion #804 for Problem #12170. Minimum Product
Type: Editorial
Status: Open
Posted by: yushanen
Posted at: 2026-01-26 19:57:56
Last updated: 2026-01-27 09:14:49
QOJ12170 题解
Comments
No comments yet.