[s2 - 8주차 - 3] 운동

[soheeGit]

문제

• 문제 사이트: 백준
• 문제 이름: 운동
• 문제 번호: 1956

문제 풀이 템플릿

### 시간복잡도 생각해보기
- 

### 풀이 아이디어
- 

### 의사코드 / 풀이 과정
- 

[soheeGit]

시간복잡도 생각해보기

• O(V³)

풀이 아이디어

• 플로이드 워셜로 풀었다.
• 모든 정점 쌍의 최단거리 dp[i][j] 를 구한다.

의사코드 / 풀이 과정

• 핵심 메소드

static void solve() {
    for(int k=0; k<V; k++) {
        for(int i=0; i<V; i++) {
            if (dp[i][k] == Integer.MAX_VALUE) continue;
            for(int j=0; j<V; j++) {
                if (dp[k][j] == Integer.MAX_VALUE) continue;
                dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k][j]);
            }
        }
    }
}