글 읽기 - 채점기에서는 런타임 에러가나는데 테스트 케이스는 잘 돌아갑니다

imscs22 7년 전 0

제곧내이지만 테스트케이스는 정답까지 잘 동작합니다만 채점기에서는 런타임에러를 발생시킵니다ㅠㅠ

어느 라인이 문제가 되는지 알려주시면 감사하겠습니다ㅠㅠ

#include <iostream>
#include <queue>
#include <cmath>
using namespace std;
int dt[20001][20001]={{0,}};
unsigned long long store[20001]={0,};
int V,e;
queue< pair< int,unsigned long long > > q;
void flushQ(){
while(q.size())q.pop();
}
int main(){
cin>>V>>e;
int dth;
cin>>dth;
dth--;
for(int i=0;i<e;i++){
int u,v,w;
cin>>u>>v>>w;
dt[u-1][v-1]=w;
}
for(int i=0;i<V;i++){
flushQ();
q.push(make_pair(dth,0));
int visit =0;
while(q.size()){
const pair<int,unsigned long long> fr = q.front();
if(fr.first==i){
 if(visit){
   store[i]=min(store[i],fr.second);
 }else{
   store[i]= fr.second;
   visit=1;
}
}
else{
for(int j=0;j<V;j++){
const int tmp = dt[fr.first][j];
if(tmp){
q.push(make_pair(j,fr.second+tmp));
}
}}
if(q.size())
q.pop();
}

}
for(int i=0;i<V;i++){
if(!store[i]&&i!=dth){
 cout<<"INF";
}
else{
cout<<store[i];
}
cout<<endl;
}
return 0;
}

bupjae 7년 전 1

dt 배열의 크기가 20001 * 20001 * 4 = 약 1500 MB로, 문제 제한인 128MB 를 훨씬 초과하고 있습니다.

입력 데이터를 저장하기 위한 다른 자료구조를 사용하셔야 합니다.

imscs22 7년 전 0

아그러네요

메모리 초과하면 채점기에서 메모리 초과라고 뜨는 걸로 알고있었는데 일단 한번 시도해봐야겠네요

감사합니다 :)

codeonwort 7년 전 1

그래프를 인접 행렬이 아니라 다음과 같이 인접 리스트로 표현해보세요.

const int MAX = 20001;
vector<int> G[MAX]; // G[i]는 i와 인접한 정점들의 목록

imscs22 7년 전 0

그렇군요 감사합니다!

좋은 연말 보내시길 바랍니다 :)

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

문제

문제

출처

ICPC

채점기에서는 런타임 에러가나는데 테스트 케이스는 잘 돌아갑니다

imscs22 7년 전 0

bupjae 7년 전 1

imscs22 7년 전 0

codeonwort 7년 전 1

imscs22 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말