|
试题描述
|
|
给定一个 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 时表示未设油库。各行相邻两个数以空格分隔。 |
|
输出
|
|
程序运行结束时,输出最小费用。
|
|
输入示例
|
|
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≤n≤100 2≤k≤10 |
是一道网络流的模板题，然而并不会写，只好退而求其次，写一个SPFA+分层图
听说还可以用BFS+优化过，也不知道是哪位高人
板子就没什么好说的了
唯一要注意的是dis[i][j][k]代表的是当汽车走到(x,y)时，所剩油量为k的最小花费
还有分类讨论
当还有油时
如果下一个点是加油站，就直接过去
如果不是
如果油够，就过去
不够，就建一个加油站
没有油了，就建一个加油站再过去
下面给出代码：
#include<iostream> #include<algorithm> #include<cstdio> #include<cstdlib> #include<cstring> #include<string> #include<cmath> #include<queue> using namespace std; inline int rd() { 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; } void write(int x) { if(x<0) putchar('-'),x=-x; if(x>9) write(x/10); putchar(x%10+'0'); return ; } int n,k,a,b,c; int map[106][106]; int dis[106][106][12],book[106][106][12]; struct node { int x,y,v; }; queue <node> q; void gt(int h1,int h2,int h3) { node hh; hh.x=h1; hh.y=h2; hh.v=h3; q.push(hh); } int dx[5]={0,0,1,0,-1},dy[5]={0,1,0,-1,0};//控制方向 int co[5]; void inq(int x,int y,int v,int cos) { if(dis[x][y][v]>cos)//比较是否更优 { dis[x][y][v]=cos; if(!book[x][y][v])//如果还没去过，就标记，然后进队 { book[x][y][v]=1; gt(x,y,v); } } return ; } void spfa()//SPFA模板 { dis[1][1][k]=0; gt(1,1,k); while(!q.empty()) { node now=q.front(); q.pop(); book[now.x][now.y][now.v]=0; for(int i=1;i<=4;i++) { int xx=now.x+dx[i]; int yy=now.y+dy[i]; int cos=dis[now.x][now.y][now.v]+co[i]; if(xx<=0||xx>n||yy<=0||yy>n) continue; if(now.v!=0) { if(map[xx][yy]) inq(xx,yy,k,cos+a); else { inq(xx,yy,now.v-1,cos); inq(xx,yy,k-1,cos+c+a); } } else inq(xx,yy,k-1,cos+a+c); } } return ; } int main() { n=rd(); k=rd(); a=rd(); b=rd(); c=rd(); co[3]=co[4]=b; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) map[i][j]=rd(); memset(dis,127,sizeof(dis)); spfa(); int ans=999999999; for(int i=0;i<=k;i++) ans=min(ans,dis[n][n][i]);//在到达终点的所剩所有用的情况中选最优，因为不一定省得油少就好 write(ans); return 0; }