BFS for modified shortest path Given K descriptions for bus line paths that exists to lead students between N campuses. What is the minimum cost that a student will have to goes from campus 1 to campus N ?
The itinerary of each path L is a sequence of |L|( ≥ 2 ) campuses {C1, C2, …, CL}, and each line has only one bus, which passes by all campuses of the line, following the itinerary order, stopping in each of them and making a U-turn whenever it reaches an endpoint of the itinerary, reversing the itinerary order. The transport pass costs 1$, and has to be paid by the passenger while getting onto the bus, no matter the time the passenger is going to stay in it.
Input:

The first input line consists of two integers N and K (2 ≤ N ≤ 10^4, 1 ≤ K ≤ 10^3), which represent respectively the number of campuses and the number of public transport lines created by UFFS. Each one of the K input lines following describes a transport line L and consists of the integer |L| (2 ≤ |L| ≤ 10^2) followed by the |L| identifiers Ci (1 ≤ Ci ≤ N, 1 ≤ i ≤ |L|) of the campuses by which the ship passes, wherein C1 and C|L| are the endpoints of L. For every campus A and every campus B it is guaranteed that it is possible to go from A to B.

Output:

Output the minimum cost to go from campus 1 to campus N.


To solve this i've tried a BFS. Each node has its distance updated. The algorithm takes the minimum distance found.
The code is easy to understand ?
I'm getting time limit exceeded on the judge that has this problem. How can i make this solution faster ?
#include &lt;cstdio&gt;
#include &lt;vector&gt;
#include &lt;queue&gt;
#include &lt;string.h&gt;

struct Edge{
    int d,t,c; //distance , target and color
    Edge(int _d,int _t ,int _c):d(_d),t(_t),c(_c){}
    Edge(int _t, int _c):d(0),t(_t),c(_c){}
};

using adj_list = std::vector&lt;Edge&gt;    ;
using graph    = std::vector&lt;adj_list&gt;;

unsigned int BFS(graph &amp;g, int source, int target, int max_colors){
    
    //init visited as false for every node
    bool visited[g.size()][max_colors];
    memset(visited,false,sizeof(visited));
    
    //put the source with an unexistent color(forcing int to buy all possible colors) and distance=0
    std::queue&lt;Edge&gt; q;
    q.push(Edge(0,source,0));
    
    unsigned int shortest_path = -1; //infinity
    while (!q.empty()) {
        Edge e = q.front();
        q.pop();

        //this path is already bigger than the minimum one
        if(e.d &gt; mini)
            continue;
        
        if(e.t == target){ //target node was found
            shortest_path = e.d &lt; shortest_path ? e.d : shortest_path;
            continue;
        }
        
        if(visited[e.t][e.c])
            continue;
        
        visited[e.t][e.c] = true;
        
        adj_list &amp;adj_u = g[e.t];
        for (auto &amp;v : adj_u) {
            //distance from adjacent node increases if its color is
            //different from the visited node color...
            //the target and color keeps the same
            q.push(Edge(e.d + (v.c != e.c), v.t, v.c));
        }
    }
    
    return shortest_path;
}


int main(void) {
    int n,k;
    scanf(&quot;%d %d&quot;,&amp;n,&amp;k);
    
    graph g(n + 1);
    for (int i = 1; i &lt;= k; ++i) {
        int l,u,v;
        scanf(&quot;%d %d %d&quot;,&amp;l,&amp;u,&amp;v);
    
        g[u].push_back(Edge(v,i));
        g[v].push_back(Edge(u,i));
        for (int j = 2; j &lt; l; ++j) {
            u = v;
            scanf(&quot;%d&quot;,&amp;v);
            g[u].push_back(Edge(v,i));
            g[v].push_back(Edge(u,i));
        }
    }

    
    /*
     for (int i = 0; i &lt; g.size(); ++i) {
     printf(&quot;%d : &quot;,i);
     for (int j = 0; j &lt; g[i].size(); ++j) {
     printf(&quot;%d -&gt; &quot;,g[i][j].t);
     }
     printf(&quot;\\ \n&quot;);
     }
     */
    
    printf(&quot;%u\n&quot;,BFS(g, 1, n, k + 1));
}

For example consider the following input:


9 4
6 2 3 4 6 7 9
4 1 3 4 5
3 8 3 4
2 9 8

For this case the minimum cost is 2;
Push bus lines, not edges
I feel like your breadth first search could be improved if instead of pushing single edges onto your queue, you pushed a whole bus line.  After all, the distance you are finding is the number of bus lines traversed, not the number of edges.  So a pseudocode algorithm would be:
foreach (busline b connected to vertex 0) {
    visited_busline[b] = true;
    q.push(b, 1);  // 1 = distance
}
visited_vertex[0] = true;

while (q.notEmpty()) {
    busline, distance = q.pop();

    foreach (vertex v in busline) {
        if (v == target) {
            return distance;
        }
        if (visited_vertex[v]) {
            continue;
        }
        visited_vertex[v] = true;
        foreach (busline b connected to v) {
            if (!visited_busline[b]) {
                visited_busline[b] = true;
                q.push(b, distance+1);
            }
        } 
    }
}

Then all that is left it to parse the original input so that each vertex v contains a list of bus lines that it is connected to.
Typo
This code didn't compile for me:

    if(e.d &gt; mini)
        continue;


I believe that at some point, you changed mini to shortest_path.  Also, in this line, I believe that you can use &gt;= which can help a little in reducing your search depth by 1 level:
    if(e.d &gt;= shortest_path)
        continue;