c++ - Running BFS to find shortest path from bottom to top of a graph -


i'm trying solve task, restraints: \$1 \le b,l,s \le 100 000\$. , use bfs every edge @ bottom of graph, , run bfs till reach y=0. however, when running code in compiler, timeout error. why tle error , change in code pass? 

#include <iostream> #include <algorithm> #include <vector> #include <queue> using namespace std;  int bfs(const vector< vector<int> > &g, pair<int, int> p) { queue <pair<pair<int, int>, int> > que; vector< vector<bool> > vis(100000,vector<bool>(100000,false)); //visited int x, y, k = 0; //k = distance pair <pair<int, int>, int> next, start; pair <int, int> pos; start = make_pair(make_pair(p.first, p.second), 0); que.push(start); while(!que.empty()) {     next = que.front();     pos = next.first;     x = pos.first;     y = pos.second;     k = next.second;     que.pop();      if (y == 0) {         return k;     }     if((g[x+1][y] == 1) && (vis[x+1][y] == false))     {         que.push(make_pair(make_pair(x+1, y), k+1));         vis[x+1][y] = true;     }     if((g[x][y+1] == 1) && (vis[x][y+1] == false))     {         que.push(make_pair(make_pair(x, y+1), k+1));         vis[x][y+1] = true;     }     if((g[x-1][y] == 1) && (vis[x-1][y] == false))     {         que.push(make_pair(make_pair(x-1, y), k+1));         vis[x-1][y] = true;     }     if((g[x][y-1] == 1) && (vis[x][y-1] == false))     {         que.push(make_pair(make_pair(x, y-1), k+1));         vis[x][y-1] = true;     }   } }  int main() { int b,l,s,x,y, shortestdist = 1234567; cin >> b >> l >> s; vector< pair <int, int> > p; //stones in first row vector< vector<int> > g(b, vector<int>(l,0)); for(int = 0; < s; i++) {         cin >> y >> x;         g[y][x] = 1; // stone = 1, empty = 0         if(y == b-1)             p.push_back(make_pair(x, y));     }  for(int i=0;i<p.size();++i)      {         shortestdist = min(shortestdist,bfs(g,p[i]));      } cout << shortestdist + 2 << "\n"; //add 2 because need jump shore  river @ start, , stone river @ end return 0; }

there 2 problems approach resulting in complexity of o(b*(b*l+s)).

the first problem is, run bfs b times in worst case if whole first row full of stones. have s stones , every stone has @ 4 neighbours, every call of bfs run in o(s), b times, algorithm need cases o(b*s) operations - i'm sure author of problem took care programs running time time out (after @ least 10^10 operations).

a possible solution problem start bfs stones of first row in queue. having multiple starting points can reached adding new vertex graph , connecting stones in first row. second approach not easy implementation, because of data structures using.

and (data structure) second problem: have s=10^5 elements/vertices/stones use b* l=10^10 memory units it. around 2g memory! don't know memory limits problem - much! initializing b times costs b* b*l operations in overall.

a better way use sparse data structure adjacency list. beware of filling out data structure in o(s^2) - use set o(slogs) or unordered_set o(s) running times.


Comments

Post a Comment

Popular posts from this blog

get url and add instance to a model with prefilled foreign key :django admin -

Image
i have page in each contest shown in row. each row contains contest id , link other model names have foreign key contest. news model: class news(models.model): title = models.charfield(max_length=50, null=true) description = models.textfield() time = models.timefield( default= datetime.datetime.now().time()) contest = models.foreignkey(contest) i want use admin adding , changing these models. want when user clicks on 'news' has foreign key contest id=1, shows list of news value foreign key. use {% instance in instances %} <tr class="{% cycle 'row1' 'row2' %}"> <td>{{ instance.title }}</td> <td>{{ instance.starttime }}</td> <td>{{ instance.timespan }}</td> <td>{{ instance.date }}</td> <td><a href="/adm...
Read more

css - Make div keyboard-scrollable in jQuery Mobile? -

from can tell, although jquery-mobile-powered pages can contain divs overflow set scroll or auto, , these divs can scrolled one-screen bar or mouse wheel, cannot scrolled using arrow keys, page-up/page-down, or home/end. instead, official "page" div (with data-role="page") absorbs input. perhaps other divs can't acquire focus, i'm not sure. is there way around this? edit: jsfiddle of simple example: https://jsfiddle.net/qogz0shx/ <script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.4/jquery.min.js"></script> <script src="https://ajax.googleapis.com/ajax/libs/jquerymobile/1.4.5/jquery.mobile.min.js"> </script> <link rel="stylesheet" href="https://code.jquery.com/mobile/1.4.5/jquery.mobile-1.4.5.css"/> <style> #outer { overflow:scroll; height: 50vh; width: 50vw; } #inner { height: 500vh; width: 500vw; } ...
Read more

android - Keyboard hides my half of edit-text and button below it even in scroll view -

i having trouble keyboard covers edit-text , half of button in scroll view. here's layout , please tell me how should resolve problem. many questions on topic none of them s working me. <?xml version="1.0" encoding="utf-8"?> <linearlayout xmlns:android="http://schemas.android.com/apk/res/android" android:layout_width="match_parent" android:background="@drawable/bg" android:layout_height="match_parent"> <scrollview android:layout_width="match_parent" android:fillviewport="true" android:layout_height="match_parent"> <relativelayout android:layout_width="match_parent" android:layout_height="wrap_content" android:orientation="vertical"> <linearlayout android:layout_width="match_parent" android:layout_height="w...
Read more