BOJ 13314 - 플로이드에 오타가?

BOJ 13314 - 플로이드에 오타가?

지구이씨의 코드를 보면 마지막 $K$번 째 정점에 대해서 edge relaxtion 을 안해주는 것을 알 수 있다.

그러면 $i \to K \to j$ 인 경로가 최단거리일 경우 $i \to j$ 의 경로에 대해서 정답과 다르게 나올 것이다.

그런데 $i \to j$ 로 가는 간선의 가중치가 $w$ 일 경우, $i \to K$ 와 $K \to j$ 의 간선의 가중치가 $\left\lfloor \dfrac w2 \right\rfloor$ 미만이기만 하면 된다.

void solve() {  
   int n = 100;  
   cout << n << '\n';  
   for (int y = 0; y < n; y++) {  
      for (int x = 0; x < n; x++) {  
         if (x == y) cout << 0 << ' ';  
         else if (y == n - 1 || x == n - 1) cout << 4999 << ' ';  
         else cout << 10000 << ' ';  
      }  
      cout << endl;  
   }  
}