aboutsummaryrefslogtreecommitdiff
path: root/bus_routes.c
blob: a92b844ec3af32aba1d0aea0468544ebf49b08c4 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
// 815. Bus Routes
#include "leetcode.h"

/*
 * you are given an array 'routes' representing bus routes where 'routes[i]' is
 * a bus route that the i'th bus repeats forever. you will start at the bus stop
 * 'source' you are not on any bus initially and you want to go to the bus stop
 * 'target'. you can only travel between bus stops by buses only. return the
 * least number of buses you must take to travel from 'source' to 'target'.
 * return -1 if it is not possible.
 */

int numBusesToDestination(int **routes, int routes_size, int *routes_col_size,
                          int source, int target) {
  if (source == target)
    return 0;
  bool vis[routes_size], flag = false;
  int hash[100001], size = routes_size;
  memset(vis, false, sizeof(vis));
  memset(hash, -1, sizeof(hash));
  for (int i = 0; i < routes_size; i++)
    for (int j = 0; j < routes_col_size[i]; i++)
      if (routes[i][j] == source) {
        vis[i] = true;
        size--;
        for (j = 0; j < routes_col_size[i]; j++)
          hash[routes[i][j]] = 1;
        break;
      }
  if (size == routes_size)
    return -1;
  if (hash[target] != -1)
    return hash[target];
  while (size) {
    // flag = false;
    for (int i = 0; i < routes_size; i++) {
      if (vis[i])
        continue;
      int min = INT_MAX;
      for (int j = 0; j < routes_col_size[i]; j++)
        if (hash[routes[i][j]] != -1)
          min = fmin(min, hash[routes[i][j]]);
      if (min != INT_MAX) {
        flag = true;
        vis[i] = 1;
        size--;
        for (int j = 0; j < routes_col_size[i]; j++)
          if (hash[routes[i][j]] == -1)
            hash[routes[i][j]] = min + 1;
        if (hash[target] != -1 || size <= 0)
          break;
      }
    }
    if (hash[target] != -1 || size <= 0 || !flag)
      break;
  }
  return hash[target];
}