6772

P6772 [NOI2020] 美食家 给你一张 \(n\) 个点 \(m\) 条边的有向图，经过每条边需要 \(w_i\) 的时间，每个点有价值 \(c_i\)。每次经过一个点时可以获得它的价值（可重复获得）。 还有 \(k\) 个附加价值 \((t, x, y)\) 表示如果你在 \(t\) 时 ......

# P6772 [NOI2020] 美食家 题解（矩阵加速图上dp常用思路） ## 简要题面 给定一张 $n$ 个点 $m$ 条单向边的图，走这条边需要花费 $w_i$ 的时间（以天为单位），现在有一个人从 $1$ 号点出发，最后回到 $1$ 号点，要求走了 **恰好** 为 $T$ 天。 每经过一 ......

观察数据范围，$T$ 很大，$n$ 很小，用矩乘。 对于一条边 $(u,v,w)$，我们将 $u$ 拆成 $w-1$ 个点，并连接 $(u_0,u_1,0),(u_1,u_2,0)...(u_{w-2},u_{w-1},0)$ 和 $(u_{w-1},v_0,c_{v})$，总点数 $5n$。 将美 ......