题目描述
给定一个 \(\text{N}\times \text{N}\) 的方形网格，设其左上角为起点◎，坐标为 \(\text{(1,1)}\) ，\(\text{X}\) 轴向右为正， \(\text{Y}\) 轴向下为正，每个方格边长为 1 ，如图所示。
一辆汽车从起点◎出发驶向右下角终点▲，其坐标为 \((\text{N},\text{N})\) 。
在若干个网格交叉点处，设置了油库，可供汽车在行驶途中加油。汽车在行驶过程中应遵守如下规则:
汽车只能沿网格边行驶，装满油后能行驶 \(\text{K}\) 条网格边。出发时汽车已装满油，在起点与终点处不设油库。
汽车经过一条网格边时，若其 \(\text{X}\) 坐标或 \(\text{Y}\) 坐标减小，则应付费用 \(\text{B}\) ，否则免付费用。
汽车在行驶过程中遇油库则应加满油并付加油费用 \(\text{A}\) 。
在需要时可在网格点处增设油库，并付增设油库费用 \(\text{C}\) (不含加油费用 \(\text{A}\) )。
\(N , K , A , B , C\) 均为正整数， 且满足约束: \(2\leq \text{N} \leq 100, 2 \leq \text{K} \leq 10\) 。
设计一个算法，求出汽车从起点出发到达终点的一条所付费用最少的行驶路线。
输入格式
文件的第一行是 \(\text{N,K,A,B,C}\) 的值。
第二行起是一个 \(\text{N}*\text{N}\) 的 0-1 方阵,每行 \(N\) 个值,至 \(\text{N}+1\) 行结束。
方阵的第 \(\text{i}\) 行第 \(\text{j}\) 列处的值为 1 表示在网格交叉点 \((\text{i},\text{j})\) 处设置了一个油库,为 0 时表示未设油库。各行相邻两个数以空格分隔。
输出格式
程序运行结束时,输出最小费用。
样例
样例输入
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
样例输出
12
数据范围与提示
\(2\leq n\leq 100\)
\(2 \leq k \leq 10\)
题解
又不是网络流
设 \(f[i][j]\) 代表到 \(i\) 号点，油量为 \(j\) 的最小代价
跑类似SPFA的东西就好了
#include<bits/stdc++.h>
#define ui unsigned int
#define ll long long
#define db double
#define ld long double
#define ull unsigned long long
const int MAXN=10000+10,MAXK=10+5,inf=0x3f3f3f3f;
int n,m,k,A,B,C,G[110][110],f[MAXN][MAXK],p[MAXN][MAXK],dr[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
struct node{
int x,y,w;
};
std::queue<node> q;
template<typename T> inline void read(T &x)
{
T data=0,w=1;
char ch=0;
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
if(ch=='-')w=-1,ch=getchar();
while(ch>='0'&&ch<='9')data=((T)data<<3)+((T)data<<1)+(ch^'0'),ch=getchar();
x=data*w;
}
template<typename T> inline void write(T x,char ch='\0')
{
if(x<0)putchar('-'),x=-x;
if(x>9)write(x/10);
putchar(x%10+'0');
if(ch!='\0')putchar(ch);
}
template<typename T> inline void chkmin(T &x,T y){x=(y<x?y:x);}
template<typename T> inline void chkmax(T &x,T y){x=(y>x?y:x);}
template<typename T> inline T min(T x,T y){return x<y?x:y;}
template<typename T> inline T max(T x,T y){return x>y?x:y;}
inline int id(int x,int y)
{
return (x-1)*n+y;
}
inline void SPFA()
{
memset(f,inf,sizeof(f));
q.push((node){1,1,k});
f[1][k]=0;
p[id(1,1)][k]=1;
while(!q.empty())
{
node pr=q.front();
q.pop();
int x=pr.x,y=pr.y,pt=id(x,y),w=pr.w;
p[pt][w]=0;
if(G[x][y]&&w!=k)
{
if(f[pt][w]+A<f[pt][k])
{
f[pt][k]=f[pt][w]+A;
if(!p[pt][k])p[pt][k]=1,q.push((node){x,y,k});
}
continue;
}
else if(!G[x][y])
{
if(f[pt][w]+C+A<f[pt][k])
{
f[pt][k]=f[pt][w]+C+A;
if(!p[pt][k])p[pt][k]=1,q.push((node){x,y,k});
}
}
if(w)
{
for(register int i=0;i<4;++i)
{
int dx=x+dr[i][0],dy=y+dr[i][1];
if(dx<1||dx>n||dy<1||dy>n)continue;
if(f[id(dx,dy)][w-1]>f[pt][w]+(i>1?B:0))
{
f[id(dx,dy)][w-1]=f[pt][w]+(i>1?B:0);
if(!p[id(dx,dy)][w-1])p[id(dx,dy)][w-1]=1,q.push((node){dx,dy,w-1});
}
}
}
}
}
int main()
{
read(n);read(k);read(A);read(B);read(C);
for(register int i=1;i<=n;++i)
for(register int j=1;j<=n;++j)read(G[i][j]);
SPFA();
int ans=inf;
for(register int i=0;i<=k;++i)chkmin(ans,f[id(n,n)][i]);
write(ans,'\n');
return 0;
}