题目描述
汽车要从（1，1）到（n，n），汽车只能在网格边上行驶，加满油时能行驶K条网格边。每次行驶时如果x坐标或y坐标减小需要支付B费用。汽车行驶经过加油站时必须加油并支付加油费用A。汽车也可以在原地设立加油站并支付C（不含加油费用A）。求最小花费。
思路
这道题依然可以用分层图做。考虑K比较小，我们就对汽车内的每种油量都建一层图。那么整个图会满足：
①每一层会与比它低一层的节点连边，并且满足连边的节点不是加油站，向右和下的边权为0，向左和上的边权为B；
②对于下一个节点是加油站的边，与最顶层连边，向右和下的边权A，向左和上的边权为A+B。
③每一个节点都可以和最顶层同一位置的节点连边，边权为C+A。
在这张图上跑一遍最短路即可。
代码
#include <bits/stdc++.h> using namespace std; const int N=2e5+10,M=N<<2; int nxt[M],head[N],to[M],w[M],tot; int mp[110][110],dis[N],k,n,num[110][110]; int dx[5]={0,0,1,-1},dy[5]={1,-1,0,0},a,b,c; bool vis[N]; void add_edge(int x,int y,int v) { nxt[++tot]=head[x]; head[x]=tot; to[tot]=y; w[tot]=v; } void build() { int s=n*n; for(int m=k;m>0;m--) { for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) for(int p=0;p<4;p++) { int x=num[i][j],y=num[i+dx[p]][j+dy[p]]; int z=y<x?b:0; if(y!=0) { if(mp[i+dx[p]][j+dy[p]]==1) add_edge(m*s+x,k*s+y,a+z); else add_edge(m*s+x,(m-1)*s+y,z); } } } for(int m=k-1;m>=0;m--) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { int x=num[i][j]; add_edge(m*s+x,k*s+x,c+a); } } void dijkstra() { priority_queue<pair<int,int> >q; memset(dis,0x3f,sizeof(dis)); dis[1+n*n*k]=0;q.push(make_pair(0,1+n*n*k)); while(!q.empty()) { int u=q.top().second;q.pop(); if(vis[u])continue ; vis[u]=1; for(int i=head[u];i;i=nxt[i]) { int v=to[i]; if(dis[v]>dis[u]+w[i]) { dis[v]=dis[u]+w[i]; q.push(make_pair(-dis[v],v)); } } } } int main() { int cnt=0; scanf("%d%d%d%d%d",&n,&k,&a,&b,&c); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) num[i][j]=++cnt; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) scanf("%d",&mp[i][j]); build(); dijkstra(); int ans=0x3f3f3f3f; for(int i=0;i<=k;i++) ans=min(ans,dis[(i+1)*n*n]); printf("%d",ans); return 0; }