传送门 ↬\looparrowright

题目描述

给定一个 n×nn \times n 的方形网格，设其左上角为起点◎，坐标 (1,1)(1,1)，XX 轴向右为正，YY 轴向下为正，每个方格边长为 11，如图所示。
FHWSPaz41e-compress.jpg
一辆汽车从起点◎出发驶向右下角终点▲，其坐标为 (n,n)(n,n)。
在若干个网格交叉点处，设置了油库，可供汽车在行驶途中加油。汽车在行驶过程中应遵守如下规则。汽车只能沿网格边行驶，装满油后能行驶 kk 条网格边。出发时汽车已装满油，在起点与终点处不设油库。
汽车经过一条网格边时，若其 xx 坐标或 yy 坐标减小，则应付费用 bb，否则免付费用。
汽车在行驶过程中遇油库则应加满油并付加油费用 AA。
在需要时可在网格点处增设油库，并付增设油库费用 cc（不含加油费用 aa ）。
n,k,a,b,cn,k,a,b,c 均为正整数， 且满足约束: 2⩽n⩽1002\leqslant n\leqslant 100，2⩽k⩽102 \leqslant k \leqslant 10。
设计一个算法，求出汽车从起点出发到达终点所付的最小费用。

输入格式

文件的第一行是 n,k,a,b,cn,k,a,b,c 的值。
第二行起是一个 n×nn\times 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

说明/提示

2⩽n⩽1002 \leqslant n \leqslant 100，2⩽k⩽102 \leqslant k \leqslant 10。

分析

在坐标 (x,y)(x,y) 可以有多种选择：加油、设立油库、增加坐标、减小坐标。每种选择会产生不同的花费，可以考虑分层图最短路。
建立 k+1k+1 层图，每一层图上有 n2n^2 个节点；层数从 00 开始编号，第 tt 层表示该层的所有节点代表的状态油量为 tt，0⩽t⩽k0\leqslant t\leqslant k。在网格图中位于坐标 (x,y)(x,y) 且油量为 tt 的状态对应节点 tn2+x(n−1)+ytn^2+x(n-1)+y。
车在网格图上行走，每走一步油量会减少 11，因此第 tt 层的节点要向 t−1t-1 层连边，若增大坐标，不产生费用，边权为 00，否则边权为 bb；遇到油库，必须将油加满，会产生费用 cc，因此有油库的点无条件向 kk 层的对应节点连边，边权为 cc；若节点没用油库，但是新设立油库，这时候贪心的考虑，不能走回头路再来加油，应当设立新油库后马上加油，费用为 b+cb+c，因此无油库的点向 kk 层的对应节点连边，边权为 b+cb+c。初始状态代表的节点为 kn2+1kn^2+1，建完图后使用 Dijkstra\text{Dijkstra} 算法即可求出图上的单源最短路，答案取 min⁡1⩽t⩽k+1dis(tn2,kn2+1),t∈N∗\min\limits_{1\leqslant t\leqslant k+1} \mathrm{dis}(tn^2,kn^2+1),t\in \mathbb{N^\ast} 即可，dis(a,b)\mathrm{dis}(a,b) 指 a,ba,b 两节点间的最短距离。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
/******************************************************************
Copyright: 11D_Beyonder All Rights Reserved
Author: 11D_Beyonder
Problem ID: 洛谷 P4009
Date: 7/26/2020 
Description: The Shortest Path In Layered Graph 
*******************************************************************/
#include<iostream>
#include<queue>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=103;
int n,k;
int a;//加油费用
int b;//坐标减小费用
int c;//增设油库费用
struct E
{
	int to;
	int dis;
	int Next;
}edge[N*N<<8];
int head[N*N<<4],tot;
int dis[N*N<<4];
bool vis[N*N<<4];
struct node
{
	int id;
	int dis;
	bool operator<(const node &x)const
	{
		return x.dis<dis;
	}
};
void init();
inline int ID(int,int,int);
inline void add_edge(int,int,int);
int dijkstra(int);
int main()
{
	cin>>n>>k>>a>>b>>c;
	init();
	int i,j,t;
	//若要加油，直接与油量为k的节点建边
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=n;j++)
		{
			bool gas;
			cin>>gas;
			//有加油站就不需要支付设立油库的费用。
			//若设立了油库，直接加油是最优的；
			//因为不能走回头路回来加油。
			if(gas)
			{
				for(t=0;t<k;t++) add_edge(ID(i,j,t),ID(i,j,k),a);
				//存在油库必须加满油
				//走到第k才层后
				//只能在第k层上建边
				if(i<=n-1) add_edge(ID(i,j,t),ID(i+1,j,k-1),0);
				if(j<=n-1) add_edge(ID(i,j,t),ID(i,j+1,k-1),0);
				if(i>=2) add_edge(ID(i,j,k),ID(i-1,j,k-1),b);
				if(j>=2) add_edge(ID(i,j,k),ID(i,j-1,k-1),b);
			}
			else
			{
				for(t=0;t<k;t++) add_edge(ID(i,j,t),ID(i,j,k),a+c);
				//无油库节点可有多种选择
				for(t=1;t<=k;t++)
				{
					if(i<=n-1) add_edge(ID(i,j,t),ID(i+1,j,t-1),0);
					if(j<=n-1) add_edge(ID(i,j,t),ID(i,j+1,t-1),0);
					if(i>=2) add_edge(ID(i,j,t),ID(i-1,j,t-1),b);
					if(j>=2) add_edge(ID(i,j,t),ID(i,j-1,t-1),b);
				}
			}
		}
	}
	cout<<dijkstra(ID(1,1,k))<<endl;
	return 0;
}
void init()
{
	memset(head,-1,sizeof(head));
	tot=0;
	memset(dis,0x3f,sizeof(dis));
	memset(vis,0,sizeof(vis));
}
inline int ID(int x,int y,int t) {return t*n*n+(x-1)*n+y;}
inline void add_edge(int u,int v,int w)
{
	tot++;
	edge[tot].to=v;
	edge[tot].dis=w;
	edge[tot].Next=head[u];
	head[u]=tot;
}
int dijkstra(int s)
{
	dis[s]=0;
	int i;
	priority_queue<node>q;
	q.push(node{s,0});
	while(!q.empty())
	{
		node now=q.top();
		q.pop();
		int x=now.id;
		if(vis[x]) continue;
		vis[x]=1;
		for(i=head[x];~i;i=edge[i].Next)
		{
			int y=edge[i].to;
			if(!vis[y]&&dis[y]>dis[x]+edge[i].dis)
			{
				dis[y]=dis[x]+edge[i].dis;
				q.push(node{y,dis[y]});
			}
		}
	}
	int ans=0x3f3f3f3f;
	for(i=0;i<=k+1;i++) ans=min(ans,dis[ID(n,n,i)]);
	return ans;
}