10076

Problem description error:

∆T = ⌈β2(h2 − h1)⌉ + γ, if h1 < h2 , here if we use  γ as problem description,we get WA from online judge,so use δ here to get accepted.

#include <iostream>
#include <queue>
#include <cstdio>
#include <cstring>
#include <cmath>

#define INF 100000000

using namespace std;

int M,N;
int gr[20][20];
int dirx[4]={1,0,0,-1};
int diry[4]={0,1,-1,0};
float alpha1,alpha2;
int gema;
float beta1,beta2;
int delta;
int Rs,Cs,Rt,Ct;
int E;
int Time[20][20][205];
bool visit[20][20][205];
int MX;

struct State{
	int x,y,_energy,_time;
};


struct cmp{
	bool operator()(State one,State two)
	{
		return one._time<two._time;
	}
};

bool bfs()
{
	priority_queue<State,vector<State>,cmp> q;
	MX = INF;
	int valu,tt;

	for(int i=0;i<20;i++)
	{
		for(int j=0;j<20;j++)
		{
			for(int k=0;k<205;k++)
			{
				Time[i][j][k]=0;
				visit[i][j][k]=false;
			}
		}
	}

	visit[Rs][Cs][0]=1;
	State stat;
	stat.x = Rs;stat.y = Cs,stat._energy = 0; stat._time = 0;

	q.push(stat);
	int r,c,en,tm;
	Time[Rs][Cs][0]=0;
	bool Found=0;
	while(!q.empty())
	{
		State tstat = q.top();
		q.pop();

		r = tstat.x;//q.front();q.pop();
		c = tstat.y;//q.front();q.pop();
		en = tstat._energy;//q.front();q.pop();
		tm = tstat._time;
		if(r==Rt && c==Ct)
		{
			if(tm<MX)
			{
				MX = tm;//Time[r][en];
				Found = 1;
			}
			continue;
		}

		for(int i=0;i<4;i++)
		{
			if(r+dirx[i]>=1 && r+dirx[i]<=M && c+diry[i]>=1 && c+diry[i]<=N)
			{
				if(gr[r]>gr[r+dirx[i]]])
				{
					valu = ceilf((gr[r]-gr[r+dirx[i]]])*alpha1)+gema;
					tt = ceilf((gr[r]-gr[r+dirx[i]]])*beta1)+delta;
				}
				else if(gr[r]<gr[r+dirx[i]]])
				{
					valu = ceilf((gr[r+dirx[i]]]-gr[r])*alpha2)+gema;
					tt = ceilf((gr[r+dirx[i]]]-gr[r])*beta2)+delta;//gema
				}
				else if(gr[r]==gr[r+dirx[i]]])
				{
					valu = gema;
					tt = delta;
				}

				if(en+valu>E)
					continue;
				if(visit[r+dirx[i]]][en+valu])
					continue;
				visit[r+dirx[i]]][en+valu] = 1;
				Time[r+dirx[i]]][en+valu] = tm+tt;//Time[r][en]+tt;

				tstat.x = r+dirx[i];
				tstat.y = c+diry[i];
				tstat._energy = en+valu;
				tstat._time = tm+tt;//Time[r+dirx[i]]][en+valu];
				q.push(tstat);
			}

		}
	}

	return Found;
}

int main()
{
	while(cin>>M)
	{
		cin>>N;

		if(M+N==0)
		break;
		cin>>alpha1>>alpha2>>gema;
		cin>>beta1>>beta2>>delta;

		for(int i=1;i<=M;i++)
		{
			for(int j=1;j<=N;j++)
				cin>>gr[i][j];
		}
		cin>>Rs>>Cs>>Rt>>Ct>>E;
		if(!bfs())
		cout<<"failed\n";//failed
		else
		cout<<MX<<"\n";
	}
	return 0;
}