글 읽기 - 플로이드 작성시 메모리초과

heehcs 7년 전 0

플로이드로 모든 쌍에대해서 구한다음

시작지점에서 다른지점까지의 거리를 출력했는데

메모리 초과가 나네요.

플로이드로는 풀리지 않는 문제인가요?

#include <cstdio>
#include <vector>
#include <utility>
using namespace std;
int a[20001][20001];
int main(){
    int n, m, s;
    scanf("%d %d %d", &n, &m, &s);
     for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            a[i][j] = 11;
            if(i == j){
                a[i][j] = 0;
            }
        }
    }
    for(int i = 0; i < m; i++){
        int u, w, v;
        scanf("%d %d %d", &u, &w, &v);
        a[u][w] = v;
    }
    int i,j,k;
    for(k = 1; k <= n; k++){
        for(i = 1; i <= n; i++){
            for(j = 1; j <= n; j++){
                if(a[i][j] > a[i][k]+a[k][j]) 
                   a[i][j] = a[i][k]+a[k][j];
            }
        }
    }
    for(int j = 1; j<= n; j++){
        if(a[s][j] == 11){
            printf("%s\n","inf");
        }else{
            printf("%d\n", a[s][j]);
        }
    }
}

codeonwort 7년 전 1

int a[20001][20001];

20001 * 20001 * 4 bytes = 1526.03 MB로 문제의 메모리 제한인 128 MB를 초과합니다.

codeonwort 7년 전 1

데이크스트라 최단경로 알고리즘의 O(E * logV) 버전을 시도해보세요.

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

문제

문제

출처

ICPC

플로이드 작성시 메모리초과

heehcs 7년 전 0

codeonwort 7년 전 1

codeonwort 7년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말