首先正向跑一遍1為起點的最短路，注意松弛過程如果走到加油站則dis=0，並且路上任意時刻dis都不能大於C，判斷dis[n]是否<=C就能判斷無解情況了。
然後反向建圖再跑一次N為起點的最短路，這樣可以求到每個點到n點的最短路。
對於每一個可以交易的城市，C-dis1[i]-dis2[i]就是多出來可以賣掉的油。
#include#include #include #include #include #include #include using namespace std; #define maxn 5005 #define maxm 200005 struct node { int v,w,next; }edge[maxm]; int head[maxn+maxn]; bool in[maxn]; int dis[maxn]; bool fuel[maxn]; int money[maxn]; int a,b,c,n,m,id; int co; void add(int a,int b,int c) { edge[id].v=b; edge[id].w=c; edge[id].next=head[a]; head[a]=id++; } void init() { memset(fuel,0,sizeof(int)*(n+1)); memset(head,-1,sizeof(int)*(n+1)); memset(money,0,sizeof(int)*(n+1)); id=0; } void SPFA(int st) { queue Q; memset(in,0,sizeof(int)*(n+1)); memset(dis,0x3f,sizeof(int)*(n+1)); Q.push(st); in[st]=1; dis[st]=0; int tmp; while(!Q.empty()) { tmp=Q.front();Q.pop(); in[tmp]=0; for(int i=head[tmp];i!=-1;i=edge[i].next) { if(dis[edge[i].v]>dis[tmp]+edge[i].w&&dis[tmp]+edge[i].w<=co) { dis[edge[i].v]=dis[tmp]+edge[i].w; if(fuel[edge[i].v]) dis[edge[i].v]=0; if(!in[edge[i].v]) { in[edge[i].v]=1; Q.push(edge[i].v); } } } } } int save[maxm][3]; int savedis[maxn]; int main() { int a,b,d; while(~scanf("%d%d%d",&n,&m,&co)) { init(); for(int i=1;i<=m;i++) { scanf("%d%d%d",&a,&b,&d); save[i][0]=a; save[i][1]=b; save[i][2]=d; add(a,b,d); } scanf("%d",&a); for(int i=1;i<=a;i++) { scanf("%d",&b); fuel[b]=1; } scanf("%d",&a); for(int i=1;i<=a;i++) { scanf("%d%d",&b,&d); money[b]=d; } SPFA(1); if(dis[n]>co) puts("-1"); else { int ans=0; id=0; memset(head,-1,sizeof(head)); memcpy(savedis,dis,sizeof(dis)); for(int i=1;i<=m;i++) add(save[i][1],save[i][0],save[i][2]); SPFA(n); for(int i=1;i<=n;i++) { if(money[i]&&dis[i]<=co&&savedis[i]<=co) { ans=max(ans,(co-savedis[i]-dis[i])*money[i]); } } printf("%d\n",ans); } } return 0; } /* 5 6 10 1 2 4 1 4 1 4 3 1 2 5 1 4 5 2 3 2 1 1 3 1 2 2 */
