출력 초과는 정답 출력 파일 크기의 2배가 넘는 출력을 할 경우 주어지는 것으로 알고 있습니다.

그 말은, 예를 들어 비용이 모두 1인데 1000000을 출력하는 경우에도 출력 초과가 발생할 수 있다는 뜻입니다.

이 문제는 단순한 BFS로는 풀리지 않습니다. 다음 반례를 참고하시면 좋겠습니다. https://www.acmicpc.net/board/... 다만 가중치의 범위가 1 이상 10 이하로 제한되어 있으므로 BFS의 확장판을 사용할 수는 있습니다. 0-1 BFS라고 하여 가중치가 0 또는 1로만 주어진 그래프에서 최단거리를 구하는 알고리즘이 있는데, 이 알고리즘은 지금까지 값이 확정된 정점 중 가장 거리가 먼 정점의 거리를 d라고 할 때, 현재 찾은 최단거리가 d 또는 d+1인 정점을 각각 따로 추적합니다. 현재 문제에서는 가중치가 10 이하이므로, 현재 찾은 최단거리가 d, d+1, ..., d+10인 정점 목록을 각각 들고 있어야 합니다. 즉 0-1 BFS의 확장판을 구현해야 합니다.

물론, 보다 보편적인 접근은 Dijkstra입니다.

========

코드를 읽어보면 간선의 weight를 수정하고 있는 것 같습니다. 이는 다소 위험해 보입니다. 왜냐면, 한 정점 u가 갱신될 때 u에서 나가는 간선의 가중치에 현재 비용 c를 더해주게 되면, 정점 u가 비용 c' (< c)로 다시 갱신되는 시점에서 간선의 가중치에 c'을 다시 더함으로써 c + c'이 더해지는 문제가 생기기 때문입니다.

감사합니다 써주신 글보고 다시 생각해보니까 로직이 많이 잘못됬네요 다시 생각해 봐야겠습니다 ㅠㅠ