BFS for modified shortest path

Question

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 <cstdio>
#include <vector>
#include <queue>
#include <string.h>
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<Edge> ;
using graph = std::vector<adj_list>;
unsigned int BFS(graph &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<Edge> 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 > mini)
 continue;
 
 if(e.t == target){ //target node was found
 shortest_path = e.d < shortest_path ? e.d : shortest_path;
 continue;
 }
 
 if(visited[e.t][e.c])
 continue;
 
 visited[e.t][e.c] = true;
 
 adj_list &adj_u = g[e.t];
 for (auto &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("%d %d",&n,&k);
 
 graph g(n + 1);
 for (int i = 1; i <= k; ++i) {
 int l,u,v;
 scanf("%d %d %d",&l,&u,&v);
 
 g[u].push_back(Edge(v,i));
 g[v].push_back(Edge(u,i));
 for (int j = 2; j < l; ++j) {
 u = v;
 scanf("%d",&v);
 g[u].push_back(Edge(v,i));
 g[v].push_back(Edge(u,i));
 }
 }
 
 /*
 for (int i = 0; i < g.size(); ++i) {
 printf("%d : ",i);
 for (int j = 0; j < g[i].size(); ++j) {
 printf("%d -> ",g[i][j].t);
 }
 printf("\\ \n");
 }
 */
 
 printf("%u\n",BFS(g, 1, n, k + 1));
}

For example consider the following input:

Bus lines

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;

Answer 1

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 > mini)
 continue;

I believe that at some point, you changed mini to shortest_path. Also, in this line, I believe that you can use >= which can help a little in reducing your search depth by 1 level:

 if(e.d >= shortest_path)
 continue;

• Felipe: I've added the e.d > mini while i was writing the post =) I will try to follow your idea.