题面戳我
题目描述
给定一个 \(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;
}

版权声明:本文为zhoushuyu原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://www.cnblogs.com/zhoushuyu/p/8178934.html