If the cost of the edge between
1
andN
isA
.1) if
A<B
, then the lowest cost will beA
.2) if
A>B
, then use BFS to find the fewest hops from1
toN
through only the edges with costB
. Assume that there are at lestL
edges between1
andN
, then returnmin(LB,A)
. It is typicalBFS
and the cost isO(N+K)
.If the edge between
1
andN
isB
.1) if 'A>B', then the answer is
B
.2) Find the fewest hops from
1
toN
only using the edge with costA
. LetS[h]
be the set of vertices can be reached byh
hops andS'
be the set have not reached yet, then it can be solved as follows.min_dis() { S[0] = {1}; int h = 0; S'={2,...,N}; while (S[h] is not empty) { S[h+1] = {}; for_each (v1 in S'){ for (v2 in S[h]) { if (cost[v1][v2] == A) { S[h+1].insert(1); S'.remove(v1); if (v1 == N) return min((h+1)*A, B); break; } } } h++; } return B; }
We can proof that this algorithm is also
O(N+K)
, since each time we testconst[v1][v2]==A
istrue
, the size ofS'
will be decreased by1
and there are at mostK
time when this test isfalse
because there are at mostK
edge with costB
. So it guarantees to be finished withO(N+K)
In total, the algorithm is O(N+K)
, which will guarantee the 2sec
time limit.