汽车加油行驶问题
时间： 1ms 内存：64M
描述：
给定一个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均为正整数。
求汽车从起点出发到达终点的一条所付费用最少的行驶路线。
输入：
输入数据件的第一行是N，K，A，B，C的值，2 ≤N≤100，2 ≤ K ≤10。第二行起是一个N*N 的0-1方阵，每行N 个值，至N+1行结束。方阵的第i行第j 列处的值为1 表示在网格交叉点（i，j）处设置了一个油库，为0 时表示未设油库。各行相邻的2 个数以空格分隔。
输出：
将找到的最优行驶路线所需的费用，即最小费用输出。输出只有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示例输出：
12提示：
参考答案（内存最优[10156]）：
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
using namespace std;
const int MAXL=101,MAXK=11,MAXN=MAXL*MAXL*MAXK,MAXM=MAXN*5,INF=~0U>>1;
const int dx[]={1,0,-1,0},dy[]={0,1,0,-1};
struct BinaryHeap
{
struct HeapElement
{
int id,value;
}H[MAXN];
int Position[MAXN],size;
BinaryHeap()
{
H[0].id=size=0;
H[0].value=-INF;
}
void Shift(int pos,int id,int value)
{
int i,f;
HeapElement p={id,value};
for (i=pos;p.value < H[f=i>>1].value;i=f)
{
H[i] = H[f];
Position[H[i].id]=i;
}
H[i] = p;
Position[H[i].id]=i;
}
void insert(int id,int value){Shift(++size,id,value);}
void decrease(int id,int value){Shift(Position[id],id,value);}
void delmin()
{
int i,c;
HeapElement p = H[size--];
for (i=1;(c=i<<1)<=size;i=c)
{
if (c+1 <=size && H[c+1].value < H[c].value)
c++;
if (H[c].value < p.value)
{
H[i] = H[c];
Position[H[i].id]=i;
}
else
break;
}
H[i] = p;
Position[H[i].id]=i;
}
}Heap;
struct edge
{
edge *next;
int t,c;
}*V[MAXN],ES[MAXM];
int N,K,A,B,C,EC,Ans,Maxflow,Total;
int dist[MAXN];
bool oil[MAXL][MAXL],vis[MAXN];
inline void addedge(int a,int b,int c)
{
ES[++EC].next = V[a]; V[a]=ES+EC; V[a]->t=b; V[a]->c=c;
}
inline int Point(int x,int y,int d)
{
return d * N * N + (x - 1) * N + y;
}
void init()
{
int i,j,k,l,c,x,y;
// freopen("trav.in","r",stdin);
// freopen("trav.out","w",stdout);
scanf("%d%d%d%d%d",&N,&K,&A,&B,&C);
for (i=1;i<=N;i++)
for (j=1;j<=N;j++)
{
scanf("%d",&c);
oil[i][j] = c;
}
for (i=1;i<=N;i++)
{
for (j=1;j<=N;j++)
{
for (l=0;l<=K;l++)
{
c = oil[i][j] ? A : A+C;
if (l<K)
addedge(Point(i,j,l),Point(i,j,K),c);
if ((!oil[i][j] && l>0) || l==K)
{
for (k=0;k<4;k++)
{
x = i + dx[k];
y = j + dy[k];
c= k<2 ? 0 : B;
if (x>=1 && x<=N && y>=1 && y<=N)
addedge(Point(i,j,l),Point(x,y,l-1),c);
}
}
}
}
}
}
void Dijkstra(int S)
{
int i,j;
for (i=1;i<=Total;i++)
Heap.insert(i,dist[i] = INF);
Heap.decrease(S,dist[S] = 0);
for (i=S;;)
{
Heap.delmin();
for (edge *e=V[i];e;e=e->next)
{
j=e->t;
if (dist[i] + e->c < dist[j])
Heap.decrease(j,dist[j] = dist[i] + e->c);
}
if (Heap.size==0)
break;
i=Heap.H[1].id;
}
}
void solve()
{
int i,a;
Total = Point(N,N,K);
Dijkstra(Point(1,1,K));
Ans = INF;
for (i=0;i<=K;i++)
if ((a=dist[Point(N,N,i)]) < Ans)
Ans = a;
}
int main()
{
init();
solve();
printf("%d\n",Ans);
return 0;
}参考答案（时间最优[164]）：
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
using namespace std;
const int MAXL=101,MAXK=11,MAXN=MAXL*MAXL*MAXK,MAXM=MAXN*5,INF=~0U>>1;
const int dx[]={1,0,-1,0},dy[]={0,1,0,-1};
struct BinaryHeap
{
struct HeapElement
{
int id,value;
}H[MAXN];
int Position[MAXN],size;
BinaryHeap()
{
H[0].id=size=0;
H[0].value=-INF;
}
void Shift(int pos,int id,int value)
{
int i,f;
HeapElement p={id,value};
for (i=pos;p.value < H[f=i>>1].value;i=f)
{
H[i] = H[f];
Position[H[i].id]=i;
}
H[i] = p;
Position[H[i].id]=i;
}
void insert(int id,int value){Shift(++size,id,value);}
void decrease(int id,int value){Shift(Position[id],id,value);}
void delmin()
{
int i,c;
HeapElement p = H[size--];
for (i=1;(c=i<<1)<=size;i=c)
{
if (c+1 <=size && H[c+1].value < H[c].value)
c++;
if (H[c].value < p.value)
{
H[i] = H[c];
Position[H[i].id]=i;
}
else
break;
}
H[i] = p;
Position[H[i].id]=i;
}
}Heap;
struct edge
{
edge *next;
int t,c;
}*V[MAXN],ES[MAXM];
int N,K,A,B,C,EC,Ans,Maxflow,Total;
int dist[MAXN];
bool oil[MAXL][MAXL],vis[MAXN];
inline void addedge(int a,int b,int c)
{
ES[++EC].next = V[a]; V[a]=ES+EC; V[a]->t=b; V[a]->c=c;
}
inline int Point(int x,int y,int d)
{
return d * N * N + (x - 1) * N + y;
}
void init()
{
int i,j,k,l,c,x,y;
// freopen("trav.in","r",stdin);
// freopen("trav.out","w",stdout);
scanf("%d%d%d%d%d",&N,&K,&A,&B,&C);
for (i=1;i<=N;i++)
for (j=1;j<=N;j++)
{
scanf("%d",&c);
oil[i][j] = c;
}
for (i=1;i<=N;i++)
{
for (j=1;j<=N;j++)
{
for (l=0;l<=K;l++)
{
c = oil[i][j] ? A : A+C;
if (l<K)
addedge(Point(i,j,l),Point(i,j,K),c);
if ((!oil[i][j] && l>0) || l==K)
{
for (k=0;k<4;k++)
{
x = i + dx[k];
y = j + dy[k];
c= k<2 ? 0 : B;
if (x>=1 && x<=N && y>=1 && y<=N)
addedge(Point(i,j,l),Point(x,y,l-1),c);
}
}
}
}
}
}
void Dijkstra(int S)
{
int i,j;
for (i=1;i<=Total;i++)
Heap.insert(i,dist[i] = INF);
Heap.decrease(S,dist[S] = 0);
for (i=S;;)
{
Heap.delmin();
for (edge *e=V[i];e;e=e->next)
{
j=e->t;
if (dist[i] + e->c < dist[j])
Heap.decrease(j,dist[j] = dist[i] + e->c);
}
if (Heap.size==0)
break;
i=Heap.H[1].id;
}
}
void solve()
{
int i,a;
Total = Point(N,N,K);
Dijkstra(Point(1,1,K));
Ans = INF;
for (i=0;i<=K;i++)
if ((a=dist[Point(N,N,i)]) < Ans)
Ans = a;
}
int main()
{
init();
solve();
printf("%d\n",Ans);
return 0;
}题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。