汽车加油行驶问题

汽车加油行驶问题

时间: 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;
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注