ZOJ 3794 Greedy Driver spfa

题意：

给定n个点，m条有向边，邮箱容量。

起点在1，终点在n，开始邮箱满油。

下面m行表示起点终点和这条边的耗油量（就是长度）

再下面给出一个数字m表示有P个加油站，可以免费加满油。

下面一行P个数字表示加油站的点标。

再下面一个整数Q

下面Q行 u v 表示在u点有销售站，可以卖掉邮箱里的任意数量的油，每以单位v元。

问跑到终点能获得最多多少元。

先求个每个点的最大剩余油量 f[i]，

再把边反向，求每个点距离终点的最短路 dis[i]。

然后枚举一下每个销售点即可,( f[i] - dis[i] ) * v。