感觉奶龙都写不出这样的题面翻译 /qd
查看原帖
感觉奶龙都写不出这样的题面翻译 /qd
400269
Jorisy楼主2024/10/14 19:04

建议修改题面翻译为:

给定 VV 个节点、EE 条边的带权 DAG(保证只有 11 号节点入度为 00VV 号节点出度为 00,无自环),要求找一条 11VV 的路径,保证恰有 kk 次在某个节点选择了当前可选择的边中边权最小的。最大化路径边权和。

1V5×104,1E1.5×105,1k101\le V\le 5\times10^4,1\le E\le 1.5\times10^5,1\le k\le 10,边权不超过 2×1092\times 10^9

给定 $V$ 个节点、$E$ 条边的带权 DAG(保证只有 $1$ 号节点入度为 $0$,$V$ 号节点出度为 $0$,无自环),要求找一条 $1$ 到 $V$ 的路径,保证恰有 $k$ 次在某个节点选择了当前可选择的边中边权最小的。最大化路径边权和。

$1\le V\le 5\times10^4,1\le E\le 1.5\times10^5,1\le k\le 10$,边权不超过 $2\times 10^9$。
2024/10/14 19:04
加载中...