Блог пользователя skpro19

Optimisation needed for a dfs problem
Автор skpro19, история, 7 лет назад, По-английски

I am getting a TLE on this problem using DFS. This is my submission. Can someone suggest some optimizations?

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by skpro19 (previous revision, new revision, compare).

→ Ответить
»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by skpro19 (previous revision, new revision, compare).

→ Ответить
»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Use BFS. Or simple std::sort d[] array ).

→ Ответить
  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    But why am I getting a TLE in my approach?

    → Ответить
    • »
      »
      »
      7 лет назад, # ^ |
      ← Rev. 7   Проголосовать: нравится 0 Проголосовать: не нравится 
      for (int i = 1; i <= k - 1 + (curr == start); i++) {
		if ((int)mpp[len].size()) {

            int last = mpp[len].back();
            mpp[len].pop_back();
			ans.pb({ curr, last });
			len++;
			dfs(last);
			len--;
			//mpp[len].pop_back();

		}else break;// <<<<-------------SEE
	}
      → Ответить