Do you prepare in a different way depending of an specific competitive programming contest? Please, share it in the comments!! :)

Hi Codeforces!!

I have tried this problem using Dijkstra, but it is giving me TLE :(, do you know a faster way to do it?

Thanks in advance!!! :)

-Problem Description-

You are given an undirected graph with weighted edges. You have to find the minimum length of path between vertex 0 and vertex n − 1 and the number of those paths with minimum length.

-Input-

There are many several test cases. Each test case begins with two positive integers n and m (2 ≤ n ≤ 100000, n − 1 ≤ m ≤ 100000) — the number of vertices and the number of edges in the graph. Each of the following m lines describes a corresponding edge. Each one contains three integers u, v and c (0 ≤ u, v < n, 1 ≤ c ≤ 1000) — these numbers denote an edge that connects vertices u and v and has weight c. The graph may contain multiple edges between the same pair of vertices and loops. It is guaranteed that the graph is connected.

-Output-

For each test case print one line with two numbers separated by a space, the minimum length of path between vertices 0 and n−1, and the number of paths between vertices 0 and n−1 with minimum length modulo 10^9 + 7.

-Sample Input-

5 12 4 3 3 3 2 1 0 2 2 2 0 2 0 1 4 4 1 2 4 1 5 0 1 2 3 1 1 3 3 1 2 1 1 0 3 1

-Sample Output-

4 3

Here is my code: https://ide.geeksforgeeks.org/gEDklVLLAF

*Description

John is having his vacations out of town and he decided to visit an amusement park to ride all the exciting attractions that the park has, he is very brave and loves to have adventures from time to time so he can distress from all the work he has at home.

Vacations are finishing and he will have to return home, while he was spending some time in the amusement park he realized he has to bring some souvenirs home, however, as he already have made his baggage he can take only two small items. Being the adventurer man he is, John knows exactly what he will be getting home, the first item he is interested is a fridge magnet so he can remember his trip each time he will get some food from the fridge, the other item is a keychain so that he can remember the trip each time he is going to open a door. There are several souvenir stores in the park on some of them they sell the keychain, on others they sell the fridge magnet but none of them sell both items so John needs to go to two stores to get the souvenirs he wants to bring home.

John is standing near a map of the park, the map depicts the park as a rectangular matrix divided in N x M cells where a '.' represents a cell where John can walk, a 'K' is a place where a store sells keychains a 'F' is a place where a store sells fridge magnets, a 'J' represents where John is standing and 'E' represents the exit. The map shows the amusement park attractions with a '#' and John can not walk over them. John can walk freely on any of the stores, the exit, and the starting point, but he will not exit the amusement park until he reaches the exit having bought both of the souvenirs.

Time is flying and John needs to move fast to get the two items before walking to the exit of the park. Can you help John to find the smallest number of steps he needs to make to exit the amusement park? A step is a movement John makes from the current cell to another cell. John can move between cells only if them share a side.

*Input specification

The first line contains an integer number T, the number of test cases. Each test case starts with a line containing two integer numbers N and M representing the dimensions of the park. The following N lines contain a string with exactly M characters these being one of '.', 'K', 'F', 'J', 'E', or '#'. 1 <= T <= 10 and 5 <= N,M <= 1000 The map has only a starting point for John and an exit There will be at least one store that sells keychains and one store that sells fridge magnets The map is surrounded by '#'

*Output specification

For each test case your program should print a single line with an integer number representing the minimum number of steps John has to make in order to buy both souvenirs and go to the exit. The input maps have always a solution.

/*---------------------------------------------------------------------------------------------------------------------*/

Hello Codeforces!!

I was trying to solve this problem a few weeks ago but i didn't achieve it :( , the authors of the problem say that it is possible to solve it using bfs but my code gives TLE, i think the TLE is in the size of my queue but how can i reduce it? Do you know another algorithm to solve it in time?

Thanks in advance!!

PD: if you want to submit it (http://coj.uci.cu/24h/problem.xhtml?pid=4019)

PD2: Here is my code

/*---------------------------------------------------------------------------------------------------------------------*/

include<bits/stdc++.h>

define endl '\n'

using namespace std;

int dx[] = {1 , -1 , 0 , 0}; int dy[] = {0 , 0 , 1 , -1};

int m , n;

vector < string > square;

int bfs(int a , int b) {

int xx , yy , s , cont , x , y , i , f , k;

queue < pair < int , pair < pair < int , int > , pair < int , int > > > > q;

q.push(make_pair(0 , make_pair(make_pair(a , b) , make_pair(0 , 0)))); // We start in the John's Position

while(!q.empty())
{
    cont = q.front().first;

    x = q.front().second.first.first;

    y = q.front().second.first.second;

    f = q.front().second.second.first;

    k = q.front().second.second.second;

    q.pop();

    if(square[x][y] == 'E' && f && k)
    {
        return cont; // We have visited at least the two stores and got to the exit
    }

    if(square[x][y] == 'F')
    {
        f++;
    }

    if(square[x][y] == 'K')
    {
        k++;
    }

    for(int i = 0; i < 4; i++) // in all directions on the grid
    {
        xx = x + dx[i];
        yy = y + dy[i];

        if(xx >= 0 && xx < m && yy >= 0 && yy < n && square[xx][yy] != '#')
        {

            q.push(make_pair(cont + 1 , make_pair(make_pair(xx , yy) , make_pair(f , k))));
        }
    }
}

return -1;

}

int main() {

ios_base::sync_with_stdio(false) , cin.tie(nullptr);

int t , a , b;

cin >> t;

while(t--)
{
    cin >> m >> n;

    square.resize(m);

    for(int i = 0; i < m; i++)
    {
        cin >> square[i];

        for(int j = 0; j < n; j++)
        {
            if(square[i][j] == 'J')
            {
                a = i , b = j;
            }
        }
    }

    cout << bfs(a , b) << endl;
}


return 0;

}