【网络流24题】 No.15 汽车加油行驶问题 (分层图最短路i)

时间:2021-08-06 05:32:10

【题意】

  问题描述:
给定一个 N*N 的方形网格,设其左上角为起点◎, 坐标为( 1, 1), X 轴向右为正, Y
轴向下为正, 每个方格边长为 1, 如图所示。 一辆汽车从起点◎出发驶向右下角终点▲,其
坐标为( N, N)。 在若干个网格交叉点处, 设置了油库, 可供汽车在行驶途中加油。 汽车在
行驶过程中应遵守如下规则:
(1)汽车只能沿网格边行驶,装满油后能行驶 K 条网格边。出发时汽车已装满油, 在起
点与终点处不设油库。
(2)汽车经过一条网格边时, 若其 X 坐标或 Y 坐标减小, 则应付费用 B, 否则免付费用。
(3)汽车在行驶过程中遇油库则应加满油并付加油费用 A。
(4)在需要时可在网格点处增设油库,并付增设油库费用 C(不含加油费用 A)。
(5)(1)~(4)中的各数 N、 K、 A、 B、 C 均为正整数, 且满足约束: 2 <=N <= 100, 2 <= K <= 10。
设计一个算法, 求出汽车从起点出发到达终点的一条所付费用最少的行驶路线。

【网络流24题】 No.15 汽车加油行驶问题 (分层图最短路i)

输入文件示例
input.txt
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

输出文件示例
output.txt
12

【分析】

  每天智障24小时again。。

  我在纠结要是建了加油站 又走回那个点怎么破。。。

  傻逼才走回以前那个点。。。

  对,傻逼就是我。。  

  k很小,直接表示在状态里面,那么。。分层图最短路。。

 #include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<cmath>
using namespace std;
#define Maxn 110
#define INF 0xfffffff int n,k,A,B,C;
bool g[Maxn][Maxn]; int mymin(int x,int y) {return x<y?x:y;} void init()
{
scanf("%d%d%d%d%d",&n,&k,&A,&B,&C);
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
{
int x;
scanf("%d",&x);
if(x==) g[i][j]=;
else g[i][j]=;
}
} int bx[]={,,,-,},
by[]={,,,,-},
cs[]; struct node
{
int x,y,z;
};
int dis[Maxn][Maxn][];
bool inq[Maxn][Maxn][];
queue<node > q;
void spfa()
{
while(!q.empty()) q.pop();
memset(dis,,sizeof(dis));
memset(inq,,sizeof(inq));
node ft;
int ans=INF;
ft.x=,ft.y=,ft.z=k;
q.push(ft);dis[][][k]=;inq[][][k]=;
cs[]=cs[]=;cs[]=cs[]=B;
while(!q.empty())
{
node now=q.front();
int x=now.x,y=now.y,z=now.z;
for(int i=;i<=;i++) if(x+bx[i]>=&&x+bx[i]<=n&&y+by[i]>=&&y+by[i]<=n)
{
node nn;
int c=cs[i]+dis[x][y][z];
nn.x=x+bx[i];nn.y=y+by[i];nn.z=z-;
if(nn.x==n&&nn.y==n) {ans=mymin(ans,c);continue;}
if(g[nn.x][nn.y]) nn.z=k,c+=A;
if(nn.z==) nn.z=k,c+=C+A;
if(c<dis[nn.x][nn.y][nn.z])
{
dis[nn.x][nn.y][nn.z]=c;
if(!inq[nn.x][nn.y][nn.z])
{
q.push(nn);
inq[nn.x][nn.y][nn.z]=;
}
}
}
q.pop();inq[x][y][z]=;
}
printf("%d\n",ans);
} int main()
{
init();
spfa();
return ;
}

还挺好打,只是像我这种不用脑子大代码的就要调试很久。。

【网络流24题】 No.15 汽车加油行驶问题 (分层图最短路i)

2016-11-06 19:45:09