크게 두 가지 해법이 있는 걸로 알고 있습니다.

첫 번째는 다익스트라 알고리즘을 3번 적용하는 것이고

두 번째는 입력에 기발한 처리를 해 다익스트라 알고리즘 1번만으로 답을 내는 것입니다.

어느 쪽이건 접근법은 (s -> g -> h -> t 또는 s -> h -> g -> t) = s -> t가 성립하는지를 확인하는 것입니다.

다익스트라 알고리즘을 3번 적용하는 첫 번째 해법의 경우

a와 b 간선의 값을 e[a][b], a를 기준으로 한 다익스트라 알고리즘의 b 값을 f(a)[b]라 표현하면

f(s), f(g), f(h)를 구한 다음

f(s)[g] + e[g][h] + f(h)[t] = f(s)[t] 또는 f(s)[h] + e[h][g] + f(g)[t] = f(s)[t]

이 식이 성립하는지로 t를 출력할지 판단했습니다.

이때 f(g)[h] 가 g에서 h로 직행한 값이라는 보장이 없다는 판단에,

임의의 x가 끼어들어 g -> x -> h < g -> h 일 수 있기에,

대신 e[g][h]을 넣었으나 채점 결과 오답이라고 나왔습니다.

이에 e[g][h] 대신 f(g)[h]를 대입해 보았음에도 결과는 달라지지 않았습니다.

두 번째 해법의 경우

모든 간선을 입력된 수치의 2배로 하되 지나야만 하는 간선에 한해서만 2배를 하고 1을 빼고

다익스트라 알고리즘을 한 번만 적용하여 각각의 t에 대해 s -> t가 홀수인지 아닌지로 판단합니다.

질문에는 이 해법대로 짠 코드를 실었습니다.

두 해법 모두 50%를 넘기지 못해서 정말 답답한 처지입니다.

제가 질문 게시판과 문제 페이지에서 찾아낸 테스트 케이스로는 전부 통과함을 확인했습니다.

50% 테스트 케이스에서 무엇이 걸리길래 통과하지 못하는 걸까요?

제 딴에는 가능한 한 고스란히 접근법을 코드로 옮겨냈다고 생각합니다만

몇 시간이 지나도 결과는 전혀 아니라고 말하고 있으니 착잡합니다.