Solução de Frederico Bulhões
É possível ver que esse problema é um problema de menor caminho em grafo com um limite a mais: que o dano no casco não ultrapasse o limite.
Podemos ainda usar o algoritmo de Dijkstra, porém o vetor de distância necessita de uma dimensão a mais. Em vez de $$dist[i]$$ conter a menor distância da fonte ao vértice $$i$$, nós em vez disso definimos $$dist[i][j]$$ como a menor distância partindo da fonte para o vértice $$i$$ enquanto sustentando exatamente $$j$$ de dano no casco.
Pensando nisso devemos alterar o algoritmo de Dijkstra. Normalmente após tirarmos um vértice da priority_queue, passaríamos por todos os vértices adjacentes. Para essa questão vamos considerar todos os vértices adjacentes, e também todos os possíveis valores de dano ao casco.
Podemos então passar por todos os valores possíveis de dano menores que $$k$$, e ver a menor distância para o vértice $$B$$.
Código para melhor entendimento:
https://gist.github.com/fredbr/b4fefe901516e2f40c06bac3079a786b