SPOJ, ELEVTRBL, DFS, A*, DIJISTRA

SPOJ-ELEVTRBL.cpp

#include <iostream>
#include <queue>
#include <cstring>
#include <vector>
#include <map>
using namespace std;
int f,s,g,u,d;

unsigned mini[1000005];

typedef struct _x{
  int cost, pos;
	_x(int a, int p){
		cost=a;
		pos=p;
	}
}state;

struct comp{
	bool operator()(state a, state b){
		return a.cost>b.cost;
	}
};


int fn()
{
	memset(mini, 0xff, (sizeof(int))*(f+1));
	priority_queue < state, vector<state> , struct comp > q;
	q.push(state(0,s));
	mini[s]=0;
	while(q.empty() != true){
		state a = q.top();
//		cout << a.pos << ' ' <<a.cost << endl;
		if(a.pos==g) 
			break;
		q.pop();
		if(a.pos>d && mini[a.pos-d]>mini[a.pos]+1){
			mini[a.pos-d]=mini[a.pos]+1;
			q.push(state(mini[a.pos-d],a.pos-d));
		}
		if(a.pos<=f-u && mini[a.pos+u]>mini[a.pos]+1){
			mini[a.pos+u]=mini[a.pos]+1;
			q.push(state(mini[a.pos+u],a.pos+u));
		}
	}
	if(mini[g]==-1)
		cout << "use the stairs";
	else
		cout << mini[g];
	cout << endl;
}

int main ()
{
	cin >> f >> s >> g >> u >> d;
	fn();
	return 0;
}