QkOIR1 B 题解

B - Quark and Flying Pigs

$\text{Description}$

给定一个 $n$ 个点 $m$ 条边的边带权无向图,在 $0$ 时刻你在点 $1$ 上。

假设当前是 $t$ 时刻,你在点 $v$ 上,你可以选择两种操作:

  • 仍停留在点 $v$ 上,操作后到 $t+1$ 时刻。
  • 选择一条边 $(a,b,w)$ 满足 $a=v$ 或 $b=v$,则你到这条边连接的另一个点上,操作后到 $t+w$ 时刻。

有 $k$ 条信息,每一条信息形如 $(t_i,v_i)$ 表示在 $t_i$ 时刻,点 $v_i$ 上会出现一只飞猪,其编号为 $i$,若该时刻你在 $v_i$ 上,则你捕获到了 $i$ 号飞猪。

现在你需要求出你能捕获到的飞猪数量的最大值。

$2\le n\le 200$,$1\le m\le \frac{n(n-1)}{2}$,$1\le k\le 5000$,$1\le a_i,b_i,v_i\le n$,$1\le w_i\le 1000$,$1\le t_i\le 10^9$。

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×