Hello. Below is my solution to the problem ELEVTRBL. My program can't handle large inputs, such as
1000000 1 1000000 1 1 and gets "time limit exceeded".
Is there a way to make it faster? Thank you.
#include<iostream>
#include<queue>
#include<list>
using namespace std;
void adj_list(list adj[], int f, int u, int d, int g);
void BFS(int u, int s, int g, list adj[]);
int main()
{
int f, s, g, u, d;
cin>>f>>s>>g>>u>>d;
if(s>g && d==0) cout<<"use the stairs\n";
else if(s<g && u==0) cout<<"use the stairs\n";
else if(s==g) cout<<0<<"\n";
else if(u==0 && d==0) cout<<"use the stairs\n";
else
{
list<int> *adj = new list<int>[f];
adj_list(adj, f, u, d, g);
BFS(f, s, g, adj);
}
return 0;
}
void adj_list(list adj[], int f, int u, int d, int g) //adjacency list
{
int up, down;
for(int i=0; i<f; i++)
{
up = i+u;
down = i-d;
if(up<f) adj[i].insert(adj[i].begin(), up);
if(down>=0) adj[i].insert(adj[i].begin(), down);
if(up==g || down==g) break; //if goal is found
}
return ;
}
void BFS(int f, int s, int g, list adj[])
{
int dist[f], temp;
bool visited[f];
queue Q;
for(int i=0; i<f; i++)
{
visited[i]=false;
dist[i] = -1;
}
visited[s-1] = true;
dist[s-1]=0;
Q.push(s-1);
list<int>::iterator itr;
while(!visited[g-1]) //while goal hasn't been found
{
temp = Q.front();
Q.pop();
for(itr=adj[temp].begin(); itr!=adj[temp].end(); ++itr)
{
if(!visited[*itr])
{
dist[*itr]=dist[temp]+1;
Q.push(*itr);
}
}
visited[temp] = true;
}
if(dist[g-1]==-1) cout<<"use the stairs\n";
else cout<<dist[g-1]<<"\n";
}