글 읽기 - 메모리 초과가 어디서 나는건가요?

growing 4년 전 0

메모리 초과라는 오류는 처음 만나봐서 어떻게 해결해야할지 모르겠습니다ㅠㅠ

어느 부분이 메모리 초과를 일으키는지 알려주시면 감사하겠습니다.

//
//  main.cpp
//  BackJoo
//
//  Created by 장환승 on 09/07/2019.
//  Copyright © 2019 장환승. All rights reserved.
//


#include <algorithm>
#include <vector>
#include <queue>
#include <cstdio>
#include <iostream>
#include <set>
using namespace std;

int time_cost[10000][10000];

int main() {
    printf("입력\n");
    int city , road;
    scanf("%d",&city);
    scanf("%d",&road);
    vector<int> vt[10000];
    vector<int> vt_2[10000];
    int indegree[10000]={0};
    int reverse_indegree[10000]={0};
    for(int i=0;i<road;i++){
        int st,ed,cost;
        scanf("%d %d %d",&st,&ed,&cost);
        time_cost[st-1][ed-1] = cost;
        vt[st-1].push_back(ed-1);
        vt_2[ed-1].push_back(st-1);
        indegree[ed-1]++;
        reverse_indegree[st-1]++;
    }
    int first, last;
    scanf("%d %d",&first,&last);
    
    queue<int> Q;
    queue<int> reverse_Q;

    for(int i=0;i<city;i++){
        if(indegree[i] == 0){
            Q.push(i);
        }
        if(reverse_indegree[i]==0){
            reverse_Q.push(i);
        }
    }
    
    int result[10000] = {0};
    int reverse_result[10000];
    for(int i=0;i<10000;i++){
        reverse_result[i] = -1;
    }
    for(int i=0;i<city;i++){
        int curr = Q.front();
        Q.pop();
        for(int j:vt[curr]){
            result[j] = max(result[j],time_cost[i][j]+result[i]);
            if(--indegree[j]==0){
                Q.push(j);
            }
        }
    }
    printf("%d\n",result[last-1]);
    
    reverse_result[last-1] = result[last-1];
    for(int i=0;i<city;i++){
        int curr = reverse_Q.front();
        reverse_Q.pop();
        for(int j:vt_2[curr]){
            if(reverse_result[j] == -1){
                reverse_result[j] = reverse_result[curr] - time_cost[j][curr];
            }
            else{
                reverse_result[j] = min(reverse_result[j],reverse_result[curr] - time_cost[j][curr]);
            }
            
            if(--reverse_indegree[j]==0){
                reverse_Q.push(j);
            }
        }
        
    }
    
   
    int count= 0;
    for(int i=0;i<10000;i++){
        for(int j=0;j<10000;j++){
            if(time_cost[i][j]&& result[j] == reverse_result[j] &&
               result[i] == reverse_result[i] &&
               reverse_result[j] == reverse_result[i] + time_cost[i][j]){
                count++;
            }
        }
    }
    printf("%d",count);
    
    
 
}

djm03178 4년 전 1

메모리 초과는 말 그대로 문제에 적힌 제한보다 많은 메모리를 할당받으려고 할 때 발생합니다.

time_cost가 요구하는 메모리가 얼마인지 계산해 보세요.

growing 4년 전 0

아하 그렇군요 감사합니다!

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

문제

문제

출처

ICPC

메모리 초과가 어디서 나는건가요?

growing 4년 전 0

djm03178 4년 전 1

growing 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말