题意：
给定n个点，m条有向边，邮箱容量。
起点在1，终点在n，开始邮箱满油。
下面m行表示起点终点和这条边的耗油量（就是长度）
再下面给出一个数字m表示有P个加油站，可以免费加满油。
下面一行P个数字表示加油站的点标。
再下面一个整数Q
下面Q行 u v 表示在u点有销售站，可以卖掉邮箱里的任意数量的油，每以单位v元。
问跑到终点能获得最多多少元。
先求个每个点的最大剩余油量 f[i]，
再把边反向，求每个点距离终点的最短路 dis[i]。
然后枚举一下每个销售点即可,( f[i] - dis[i] ) * v。
#include
#include
#include
#include
#include
#include
#include
using namespace std; #define N 10050 #define M 200010 #define inf 1000000 #define ll long long struct Edge{ int from, to, dis, nex; }edge[M], e[M]; int head[N],edgenum; void add(int u,int v,int d){ Edge E={u,v,d,head[u]}; edge[edgenum] = E; head[u] = edgenum++; } int H[N], edg; void add2(int u,int v,int d){ Edge E={u,v,d,H[u]}; e[edg] = E; H[u] = edg++; } int n, m, k; int F[N], T[N];//F是车站 T是贩卖点 int f[N];//起点到这里最多能剩多少油 bool inq[N]; void spfa(){ queue
q; memset(f,-1,sizeof f); memset(inq, 0, sizeof inq); f[1] = k; q.push(1); while(!q.empty()){ int u = q.front(); q.pop(); inq[u] = 0; for(int i = head[u]; ~i; i = edge[i].nex){ int v = edge[i].to; if(f[v]< f[u] - edge[i].dis){ if(F[v])f[v]=k; else f[v] = f[u] - edge[i].dis; if(!inq[v])inq[v] = 1, q.push(v); } } } } int dis[N];//把边反一下跑出距离终点的最短路，也就是从这个点到终点最少要多少油 void bfs(){ for(int i = 1; i <= n; i++)dis[i] = inf; memset(inq, 0, sizeof inq); dis[n] = 0; queue
q; q.push(n); while(!q.empty()){ int u = q.front(); q.pop(); inq[u] = 0; for(int i = H[u]; ~i ; i = e[i].nex){ int v = e[i].to; if(dis[v]>dis[u]+e[i].dis){ if(F[v])dis[v] = 0; else dis[v] = dis[u]+e[i].dis; if(!inq[v])inq[v] = 1, q.push(v); } } } } void init(){memset(head, -1, sizeof head);edgenum = 0;memset(H, -1, sizeof H);edg = 0;} int main(){ int i,u,v,d; while(~scanf("%d %d %d",&n,&m,&k)){ init(); memset(F, 0, sizeof F); memset(T, 0, sizeof T); while(m--){ scanf("%d %d %d",&u,&v,&d); add(u,v,d); add2(v,u,d); } scanf("%d",&m); while(m--){scanf("%d",&u);F[u]=1;} scanf("%d",&m); while(m--){scanf("%d %d",&u,&v);T[u]=v;} spfa(); if(f[n]==-1){puts("-1");continue;} bfs(); int ans = 0; for(int i = 1; i <= n; i++)if(T[i] && f[i]!=-1&&dis[i]