제 제출번호 96257620 는 인터넷에서 보고 유사하게 작성해서 제출한 코드인데 반례가 있습니다.

노드 번호 순대로 간선들을 순회하는데 s->e 경로가 노드 번호가 증가했다가 감소했다가 하는 구조이면 답이 나오지 않습니다.

그래서 저는 이 문제를 푸는 방법이 dist 배열을 유지하면서 T 별로 최단 거리를 구하는 것이라고 생각합니다. 근데 그건 시간초과가 나고요.

혹시 제가 문제 조건에서 놓치고 있는 것이 있는지 봐주실 수 있을까요?


읽어주셔서 감사합니다!

zenith82114   1년 전

시간별로 최단거리 배열 만들면 풀리는 거 맞습니다. 인접한 시간 간에 DP 스타일로 전이하면 되고 토글링도 가능합니다.

제출하신 코드를 봤습니다. 입력 순서대로 처리해주시던데 입력 순서가 s -> e 경로를 만들지 못하는 경우도 해결해주는 이유가 무엇인지 궁금합니다.

만약 s = 0, e = 3 이라고 할 때 아래처럼 입력이 들어오면 처리가 안되지 않나요?


2 3

0 1

1 2


답변 감사합니다!

zenith82114   1년 전

문제의 입력 형식과 달라서 어떤 입력인지 잘 모르겠네요. t회의 시각마다 m개씩의 간선이 (총 t*m개) 주어져야 합니다.

헷갈리게 하여 죄송합니다. 원래 글에 적혀있는 예제와 같은 의미라서 그 것으로 하겠습니다.

입력 순서가 안좋게 걸리면 최단 거리를 못구한다고 생각합니다. 제가 놓치고 있는 부분이 있을까요.

저는 dist 배열을 1개로 유지하면서 t마다 다익스트라를 해야한다고 생각합니다.

답변 감사합니다!

zenith82114   1년 전

경로를 구성할 때에는 각 시간 표기에서 최대 한 개의 간선을 선택할 수 있으며, 경로를 구성하는 간선들이 정의되는 시간 표기가 연속할 필요는 없다.

이 문장을 놓치신 것 같습니다. t=1일 경우 s에서 곧장 e로 가는 간선이 없으면 경로가 형성될 수 없습니다.

정말 정확히 짚어주셨습니다..

제 생각에 몰입한 나머지 필요한 부분을 못읽었네요. 덕분에 의문이 해결되었습니다.

감사합니다!!

댓글을 작성하려면 로그인해야 합니다.