【题意】
问题描述：
给定一个 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。
设计一个算法， 求出汽车从起点出发到达终点的一条所付费用最少的行驶路线。
输入文件示例
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 ;
}
还挺好打，只是像我这种不用脑子大代码的就要调试很久。。
2016-11-06 19:45:09
