题目大意

给定 $n$ 个节点的有向图，边有正权。求从节点 $0$ 到节点 $n-1$ 的最长简单路径（不重复经过节点）。

算法思路

核心思想

状态压缩动态规划，利用 $n \le 18$ 的条件，用二进制位表示已访问的节点集合。

状态设计

设 f[x][S] 表示当前位于节点 $x$，已访问节点集合为 $S$（二进制状态）时，能获得的最大路径长度。

状态转移

对于当前状态 (x, S)，枚举所有从 $x$ 出发的边 $(x, v, w)$：

如果 $v$ 不在集合 $S$ 中（即 S & (1<<v) == 0）

则转移：f[x][S] = max(f[x][S], f[v][S|(1<<v)] + w)

边界条件

当 x == n-1 时，返回 $0$（已到达终点）

初始调用：dp(0, 1)（从节点 $0$ 出发，已访问节点 $0$）

算法流程

读入建图：用邻接表存储有向边

记忆化搜索：从起点 $(0, 1)$ 开始递归计算

输出结果：f[0][1] 即为答案

复杂度分析

状态数：$O(n \cdot 2^n)$

转移复杂度：$O(\text{出度})$

总复杂度：$O(n \cdot 2^n \cdot m/n) \approx O(m \cdot 2^n)$

在 $n \le 18$ 时可行

总结

本题是状态压缩DP的经典应用：

状态设计：用二进制位表示节点访问情况

记忆化搜索：避免重复计算相同状态

有向图处理：沿有向边进行状态转移

最长路径：与最短路径对称，将 min 改为 max

这种"状态压缩 + 记忆化搜索"的方法适用于小规模图的路径计数和优化问题，是解决NP难问题的有效近似方法。