题目描述
给定一个 N imes NN×N 的方形网格，设其左上角为起点◎，坐标(1,1)(1,1)，XX 轴向右为正， YY 轴向下为正，每个方格边长为 11 ，如图所示。
一辆汽车从起点◎出发驶向右下角终点▲，其坐标为 (N,N)(N,N)。
在若干个网格交叉点处，设置了油库，可供汽车在行驶途中加油。汽车在行驶过程中应遵守如下规则:
-
汽车只能沿网格边行驶，装满油后能行驶 KK 条网格边。出发时汽车已装满油，在起点与终点处不设油库。
-
汽车经过一条网格边时，若其 XX 坐标或 YY 坐标减小，则应付费用 BB ，否则免付费用。
-
汽车在行驶过程中遇油库则应加满油并付加油费用 AA。
-
在需要时可在网格点处增设油库，并付增设油库费用 CC(不含加油费用AA )。
-
N,K,A,B,CN,K,A,B,C 均为正整数， 且满足约束: 2leq Nleq 100,2 leq K leq 102≤N≤100,2≤K≤10。
设计一个算法，求出汽车从起点出发到达终点所付的最小费用。
输入输出格式
输入格式：
文件的第一行是 N,K,A,B,CN,K,A,B,C 的值。
第二行起是一个N imes NN×N 的 0-10−1 方阵,每行 NN 个值,至 N+1N+1 行结束。
方阵的第 ii 行第 jj 列处的值为 11 表示在网格交叉点 (i,j)(i,j) 处设置了一个油库,为 00 时表示未设油库。各行相邻两个数以空格分隔。
输出格式：
程序运行结束时,输出最小费用。
输入输出样例
输入样例#1：
9 3 2 3 6 0 0 0 0 1 0 0 0 0 0 0 0 1 0 1 1 0 0 1 0 1 0 0 0 0 1 0 0 0 0 0 0 1 0 0 1 1 0 0 1 0 0 1 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 1 1 0 0 1 0 0 0 1 0 0 1 0 0 0 0 0 0 0
输出样例#1：
12
分层最短路板子题，讲在i行，j列，还剩k油为一个状态，其中建出这个点为k*n*n+i*n+j然后分出加油和跑路，跑一边SPFA即可
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <cmath> #include <cstdlib> #include <queue> #include <stack> #include <vector> using namespace std; #define MAXN 200100 #define INF 10000009 #define MOD 10000007 #define LL long long #define in(a) a=read() #define REP(i,k,n) for(int i=k;i<=n;i++) #define DREP(i,k,n) for(int i=k;i>=n;i--) #define cl(a) memset(a,0,sizeof(a)) inline int read(){ int x=0,f=1;char ch=getchar(); for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1; for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0'; return x*f; } inline void out(int x){ if(x<0) putchar('-'),x=-x; if(x>9) out(x/10); putchar(x%10+'0'); } int n,k,a,b,c; deque <int> Q; int ans=0; int dis[MAXN],vis[MAXN]; int total=0,head[MAXN<<2],nxt[MAXN<<2],to[MAXN<<2],val[MAXN<<2]; inline int calc(int l,int i,int j){ return n*n*l+n*i+j; } inline void adl(int a,int b,int c){ total++; to[total]=b; val[total]=c; nxt[total]=head[a]; head[a]=total; return ; } inline void SPFA(){ memset(dis,127,sizeof(dis)); Q.push_back(calc(k,0,0)); dis[calc(k,0,0)]=0; vis[calc(k,0,0)]=1; while(!Q.empty()){ int u=Q.front(); Q.pop_front(); vis[u]=0; for(int e=head[u];e;e=nxt[e]) if(dis[to[e]]>dis[u]+val[e]){ dis[to[e]]=dis[u]+val[e]; if(vis[to[e]]) continue; vis[to[e]]=1; if(!Q.empty()) if(dis[to[e]]<dis[Q.front()]) Q.push_front(to[e]); else Q.push_back(to[e]); else Q.push_back(to[e]); } } return ; } int main(){ in(n);in(k);in(a);in(b);in(c); REP(i,0,n-1) REP(j,0,n-1){ int x; in(x); if(x || (!i && !j)){ REP(l,0,k-1) adl(calc(l,i,j),calc(k,i,j),a); if(i!=n-1) adl(calc(k,i,j),calc(k-1,i+1,j),0); if(j!=n-1) adl(calc(k,i,j),calc(k-1,i,j+1),0); if(i) adl(calc(k,i,j),calc(k-1,i-1,j),b); if(j) adl(calc(k,i,j),calc(k-1,i,j-1),b); } else{ REP(l,0,k-1) adl(calc(l,i,j),calc(k,i,j),a+c); REP(l,1,k){ if(i!=n-1) adl(calc(l,i,j),calc(l-1,i+1,j),0); if(j!=n-1) adl(calc(l,i,j),calc(l-1,i,j+1),0); if(i) adl(calc(l,i,j),calc(l-1,i-1,j),b); if(j) adl(calc(l,i,j),calc(l-1,i,j-1),b); } } } SPFA(); ans=INF; REP(i,0,k) ans=min(ans,dis[calc(i,n-1,n-1)]); out(ans); return 0; }