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