題意：
給定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(){
queueq;
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;
queueq; 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]
