题面戳我
题目描述
给定一个 \(N×N\) 的方形网格，设其起点坐标\((1,1)\)，\(X\)轴向右为正，\(Y\)轴向下为正，每个方格边长为\(1\)，终点坐标为 \((N,N)\)。
在若干个网格交叉点处，设置了油库，可供汽车在行驶途中加油。汽车在行驶过程中应遵守如下规则:
汽车只能沿网格边行驶，装满油后能行驶 \(K\) 条网格边。出发时汽车已装满油，在起点与终点处不设油库。
汽车经过一条网格边时，若其\(X\)坐标或\(Y\)坐标减小，则应付费用 \(B\)，否则免付费用。
汽车在行驶过程中遇油库则应加满油并付加油费用 \(A\)。
在需要时可在网格点处增设油库，并付增设油库费用 \(C\)(不含加油费用\(A\) )。
\(N,K,A,B,C\)均为正整数， 且满足约束: \(2≤n≤100,2≤k≤10\)
设计一个算法，求出汽车从起点出发到达终点所付的最小费用。
输入输出格式
输入格式：
文件的第一行是\(N,K,A,B,C\)的值。
第二行起是一个\(N×N\)的\(0−1\)方阵,每行\(N\)个值,至\(N+1\) 行结束。
方阵的第 \(i\) 行第 \(j\) 列处的值为 \(1\) 表示在网格交叉点 \((i,j)\) 处设置了一个油库,为 \(0\) 时表示未设油库。各行相邻两个数以空格分隔。
输出格式：
程序运行结束时,输出最小费用。
输入输出样例
输入样例#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≤100,2≤k≤10\)

sol

这题是假的网络流，虽然说费用流也不是不可以写。。。
设\(dis_{x,y,k}\)表示到达位置在\((x,y)\)，剩余油量为\(k\)这个状态的最小代价。可知这个东西可以用\(SPFA\)转移。
所以转移即可。
注意：题目中说经过油库时若油箱不满是强制加油的。没判这个就要WA两个点（而且跑出来答案小了）

code

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int MAX = 105;
struct node{int x,y,k;};
int N,K,A,B,C,mp[MAX][MAX],dis[MAX][MAX][11],vis[MAX][MAX][11],ans;
int dx[4]={0,-1,0,1},dy[4]={-1,0,1,0};
queue<node>Q;
int gi()
{
	int x=0,w=1;char ch=getchar();
	while ((ch<\'0\'||ch>\'9\')&&ch!=\'-\') ch=getchar();
	if (ch==\'-\') w=0,ch=getchar();
	while (ch>=\'0\'&&ch<=\'9\') x=(x<<3)+(x<<1)+ch-\'0\',ch=getchar();
	return w?x:-x;
}
int main()
{
	N=gi();K=gi();A=gi();B=gi();C=gi();
	for (int i=1;i<=N;i++)
		for (int j=1;j<=N;j++)
			mp[i][j]=gi();
	memset(dis,63,sizeof(dis));
	dis[1][1][K]=0;Q.push((node){1,1,K});
	while (!Q.empty())
	{
		int x=Q.front().x;
		int y=Q.front().y;
		int k=Q.front().k;Q.pop();
		vis[x][y][k]=0;
		if (mp[x][y]&&k!=K)
		{
			if (dis[x][y][K]>dis[x][y][k]+A)
			{
				dis[x][y][K]=dis[x][y][k]+A;
				if (!vis[x][y][K]) vis[x][y][K]=1,Q.push((node){x,y,K});
			}
			continue;//就是这个continue判强制加油
		}
		else
		{
			if (dis[x][y][K]>dis[x][y][k]+C+A)
			{
				dis[x][y][K]=dis[x][y][k]+C+A;
				if (!vis[x][y][K]) vis[x][y][K]=1,Q.push((node){x,y,K});
			}
		}
		if (k)
			for (int d=0;d<4;d++)
			{
				int i=x+dx[d],j=y+dy[d];
				if (i<1||i>N||j<1||j>N) continue;
				if (d>1&&dis[i][j][k-1]>dis[x][y][k])
				{
					dis[i][j][k-1]=dis[x][y][k];
					if (!vis[i][j][k-1]) vis[i][j][k-1]=1,Q.push((node){i,j,k-1});
				}
				if (d<2&&dis[i][j][k-1]>dis[x][y][k]+B)
				{
					dis[i][j][k-1]=dis[x][y][k]+B;
					if (!vis[i][j][k-1]) vis[i][j][k-1]=1,Q.push((node){i,j,k-1});
				}
			}
	}
	ans=dis[N][N][0];
	for (int i=1;i<=K;i++)
		ans=min(ans,dis[N][N][i]);
	printf("%d\n",ans);
	return 0;
}