《Part-Time Jobs》题目分析

首先，由于有Q件任务，所以完成任务的顺序一共有Q!种。

我们可以比较简单的判断一种顺序可不可行。例如先完成任务3，再完成任务1，最后完成任务2。首先我们一定沿着从Building 1到L3的最短路达到L3，这是到达L3最早的方式。比较当前时间和任务3的时间要求([S3, E3]，花费T3)：

1. 当前时间 < S3，那么我们要等到S3开工，最早完成任务3的时间是S3+T3。
2. 当前时间 > E3，那么我们来晚了，来不及完成任务3。任务3失败，不用再判断后面的任务。
3. 否则，我们可以直接开工，最早完成任务3的时间是 当前时间+T3。

之后我们会沿着L3到L2的最短路到达任务2的地点L2，再进行以上的判断…… 直到所有任务都完成或者在某一步失败。这时可以计算获得的报酬。

这个直观的算法有两个问题： 1. 我们需要知道两个地点之间的最短路。 2. 时间复杂度还是有点高，Q!种顺序，每种顺序还要O(Q)判断。

对于第一个问题，由于学校中有N=10000个建筑，求出这些建筑两两之间的最短路复杂度很高。不过相比建筑数N，任务数Q很小，最大是20。实际上我们只用到从有任务的建筑到另一个有任务的建筑之间的最短路，以及从起点到一个有任务的建筑之间的最短路。这些我们关心的点最多有1+Q个。我们只需要以这1+Q个点为起点，在整个图上执行1+Q次单源最短路算法，就能求出这1+Q个点两两之间的最短路。这里单源最短路推荐选择SPFA，速度较快。

对于第二个问题，我们需要用到状态压缩动态规划。我们用一个整数S (0 <= S < 2^Q)来描述当前哪些任务是完成的，那些没有完成。具体来说，如果S的二进制表示的从低到高第i位是1表示，第i个任务是完成的；0表示第i个任务未完成。例如S=5，也即(101)2，表示第一个任务完成，第二个任务没完成，第三个任务完成，其余任务都没完成的状态。

我们用f[S][i]表示完成任务状态是S，并且最后完成的是第i个任务，最少花费的时间。如果我们不可能达到这种状态，则f[S][i]=-1。

通过枚举下一个任务j完成转移：f[S][i] -> f[S | 2^j][j] | S第j位不等于1。

最后我们检查所有可能的状态(S, i)。如果f[S][i]的值不是-1，就意味着我们可以通过某种顺序，完成S中的所有任务。这时报酬就是S中非0二进制位代表的任务报酬之和。