意甲冠军：
特定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 longstruct 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; //由于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]
版权声明：本文博客原创文章，博客，未经同意，不得转载。