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 <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;

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:

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 > 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;

• I've added the e.d > mini while i was writing the post =) I will try to follow your idea. Commented Oct 31, 2015 at 21:15