题目描述
给定一个 N \times 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 均为正整数， 且满足约束: 2\leq N\leq 100,2 \leq K \leq 102≤N≤100,2≤K≤10。
设计一个算法，求出汽车从起点出发到达终点所付的最小费用。
输入输出格式
输入格式：
文件的第一行是 N,K,A,B,CN,K,A,B,C 的值。
第二行起是一个N\times 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;
}
转载于:https://www.cnblogs.com/jason2003/p/9636646.html
相关资源：汽车加油行驶问题(C语言算法设计与分析)
