Solução por Pedro Racchetti
Conteúdos usados:
Para resolvermos esse problema, iremos usar o algoritmo de Dijkstra, para encontramos o menor caminho. Primeiro, iremos ler o grafo da entrada, e ao guardá-lo, guardaremos também o grafo reverso, ou seja, para toda aresta $$U$$ para $$V$$ com peso $$P$$, no grafo que chamaremos de normal, o grafo reverso terá a aresta $$V$$ para $$U$$ com peso $$P$$.
O quase menor caminho, como descrito no problema, não pode conter arestas que pertençam a um menor caminho. Portanto, podemos retirá-las do grafo, e então usar o algoritmo de Dijkstra, saindo de $$S$$ nesse grafo resultante, guardando as menores distâncias de cada vértice à vértice $$S$$ no vetor $$dfim$$; desse modo, temos que o tamanho do quase menor caminho é $$dfim[D]$$. Porém ainda não sabemos como identificar se uma aresta pertence a um menor caminho.
Para acharmos isso, podemos usar o algoritmo de Dijkstra no grafo original partindo do ponto $$S$$, e guardar as menores distâncias de cada ponto em um vetor (chamaremos-o de $$dnorm$$). Podemos então fazer o mesmo processo no grafo reverso, partindo de $$D$$ (chamaremos o novo vetor de $$drev$$). Perceba que uma aresta de $$U$$ para $$V$$, com peso $$P$$ está em um menor caminho de $$S$$ para $$D$$, se e somente se $$dnorm[U] + drev[V] + P$$ for igual à $$dnorm[D]$$.
Isto é verdade devido ao fato de que o menor caminho de $$S$$ para $$D$$ passando pela aresta $$(U, V)$$ é o mesmo que o menor caminho de $$S$$ para $$U$$, somado ao menor caminho de $$V$$ para $$D$$ e ao peso da aresta, $$P$$. Note que o menor caminho de $$S$$ para $$U$$ é guardado em $$dnorm[U]$$ e o menor caminho de $$V$$ para $$D$$ (que é o mesmo que o menor caminho de $$D$$ para $$V$$ no grafo reverso) está guardado em $$drev[V]$$.
Portanto, basta retirar todas as arestas que satisfazem essa condição, e fazer o processo descrito no segundo parágrafo.
Note que retirar arestas é equivalente a montar um novo grafo, sem essas arestas.
Segue o código, comentado, para melhor compreensão da solução.
https://gist.github.com/PedroRacchetti/5e730c6eb8dcab53cb8b8b5b911438be