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

image.png

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

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

그런데 i→ji \to j 로 가는 간선의 가중치가 ww 일 경우, i→Ki \to K 와 K→jK \to j 의 간선의 가중치가 ⌊w2⌋\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;  
   }  
}

Tags:

Categories:

Updated:

Comments

You may also enjoy