Solução por Pedro Racchetti
Conhecimentos utilizados:
Para esse problema, primeiro precisamos notar que podemos usar o algoritmo de Dijkstra, para encontrar o menor caminho de cada cidade até qualquer posto de gasolina guardaremos esse número no vetor $$dist$$. Além disso, guardamos para cada cidade, qual é o posto mais perto.
Podemos então, para cada estrada, perceber que o menor caminho que passa por ela tem tamanho $$dist[x] + dist[y] + d$$. Podemos então ordenar os caminhões e as estradas no mesmo vetor, utilizando o valor encontrado para as estradas e $$c_i$$ para os caminhões. Isso nos garante que quando chegarmos a um caminhão, todos os caminhos de um posto para outro com tamanho menor ou igual à $$c_i$$ já terão sido analisados.
Porém, como analisamos uma aresta? podemos conectar o posto mais perto da cidade $$x$$ com o posto mais perto da cidade $$y$$ no Union-Find, e para os caminhões, basta verificar se as duas extremidades das arestas estão na mesma componente!
Segue o código comentado, para melhor compreensão:
https://gist.github.com/PedroRacchetti/d01da66c4a947558468436ac3864edf0