플로이드네요

I==j인 걍우

위의 코드는 k = j+1 to n까지 보고

아래 코드같은 경우 k = 1 to n을 보는데 i==j인 경우만 스킵하네요

다시말해

j==k==3인 경우

위의 코드는 k = 4, 5, 6, ..  n

아래의 코드는 1, 2, 4, ... n(3만 빼고)

그냥 잘못 구현한거 같아요

애초에 플로이드 시간이 V^3인데 TLE가 당연해 보이네요

적어주신대로 구현도 직접해서 제출했는데 TLE나오구요

http://boj.kr/4ccc1336a61b48f7...

아래 코드로 AC를 받으셨나요?

V가 800이라 다익스트라 2번 쓰는게 정해같은데 말씀하신 풀이가 궁금하네요

답변감사합니다~

질문드렸던 코드의 경우 위쪽 코드의 의도를 설명드리자면 일단 행렬은 모두 0으로 초기화 되어있는 상태고, 양방향으로 길이 연결되어있으니 플로이드 행렬이 대각선 대칭일것이다 라는 가정하에 road[j][k] = road[k][j] 를 사용해서 한번에 요소 두개씩 갱신해주었습니다. 그래서 k=j+1에서부터 시작해도 무방하겠다는 생각이었는데,,, 안되더군요,, 하하ㅜㅜ 아래쪽 코드는 단방향 일때나 양방향일 때 모두 쓸 수 있는 일반적인 플로이드 코드가 맞습니다

플로이드로도 해결은 됐습니다 시간초과가 안나더라구요! 저도 의아해서 찾아보다가 다른 질문글에서 본건데, 플로이드가 상수항이 아주 작은 알고리즘에 속해서 시간초과가 안날 수도 있겠다는 의견을 봤습니다.

소스코드 링크 공유 처음해보는데 될지 모르겠네요ㅎㅎ;;

http://boj.kr/0b575b664c744fc3...

그런데 다익스트라 2번으로도 해결할 수 있나요?? 노드1에서 한번, N에서 한번, A나 B에서 한번 이렇게 3번 돌려야되나 생각했었는데 어떻게 두번에 해결할 수 있을지 여쭙고싶네요!

플로이드에서 가장 안쪽 for문이 도착지를 의미하니 road[j][i] + road[i][k] 이 부분에서 결과에 차이가 생길 것 같습니다(road[i][k] 이 부분) 확실히는 잘 모르겠습니다ㅠㅠ

아무튼 대각행렬일 수 있다는 말씀에 심각하게 고민해봤네요ㅎㅎ 왠지 모르게 그럴듯해보여서 고민해보니 플로이드의 결과는 그렇게 보이는데 연산 과정에서도 대각 행렬이 유지되는지 잘 모르겠네요...

또 말씀해주신대로 저도 다른 분들께 의견을 구해보니 3중 for문 안에 코드가 아주 가벼운 연산이라 이런 경우 5억번도 돌 수 있다는 의견을 들었습니다

플로이드 경우 반례도 잡기 어려워 그냥 올바른 풀이?로 생각하려 합니다(데이터 추가요청도 하긴 했는데 데이터 만들기가 난감하더라구요...)

다익스트라 2번은 그냥 문제에서 주어진 정점 2개에 대해 다익스트라를 돌리면 쉽게 풀 수 있습니다

http://boj.kr/2a11d7c1320d4083...

p.s.

소스코드는 공개해두셔서 너무 궁금하여 열어봤습니다ㅎㅎ

생각치도 못하게 새로운 내용을 알게되어 좋았습니다🙂👍👍