글 읽기 - C++ 메모리 초과 오류 질문 있습니다!

rbstj0311 2년 전 2

문제에 나와 있는 테스트 케이스는 잘 돌아가고, 60%까지는 채점이 되는데 갑자기 메모리 오류가 뜨네요... 고수님들의 지적 부탁드립니다!

혹시 vector<pair<int, int>> vertex[VERTEX_MAX]; 이 부분이 메모리를 많이 먹는 걸까요??

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

#define VERTEX_MAX 20001
#define EDGE_MAX 300001
#define INF 1000000000

int main() {
    int V, E, K; // vertex, edge, starting vertex
    int dist[VERTEX_MAX]; // starting vertex로 부터 다른 vertex까지의 최단 경로를 정리해 놓은 배열
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    vector<pair<int, int>> vertex[VERTEX_MAX]; // vertex 사이의 관계를 나타낸 vector

    cin >> V >> E;
    cin >> K;

    

    for (int i = 0; i < E; i++) {
        int u, v, w;

        cin >> u >> v >> w;

        vertex[u].push_back({w, v}); //vertex u에 대해 가중치 w, 연결된 vertex v
    }

    dist[K] = 0;

    for (int i = 1; i <= V; i++) {
        if (i == K)
            continue;
        dist[i] = INF;
    } 
    
    pq.push({dist[K], K});
    
    while (!pq.empty()) {
        int curVertex = pq.top().second;
        int curDistinPQ = pq.top().first;

        pq.pop();

        if(curDistinPQ > dist[curVertex]) 
            continue;

        for (const auto& v : vertex[curVertex]) {
            int nextVertex = v.second;
            int nextDist = v.first + curDistinPQ;

            if (nextDist < dist[nextVertex])
                dist[nextVertex] = nextDist;
                pq.push({nextDist, nextVertex});
            
        }

    }

    for(int i = 1; i <= V; i++)
        if (dist[i] == INF)
            cout << "INF\n";
        else
            cout << dist[i] << '\n';

    return 0;
}

amsminn 2년 전 4

아래의 코드에서 중괄호가 없습니다. 그래서 항상 pq.push가 실행되고 메모리 초과가 되겠네요.

if (nextDist < dist[nextVertex])
    dist[nextVertex] = nextDist;
    pq.push({nextDist, nextVertex});

rbstj0311 2년 전 4

헐... 이걸 못 봤다니 ㅠㅠ 파이썬만 하다가 저런 실수를...

매의 눈으로 실수 잡아주셔서 정말 감사합니다!!

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

문제

문제

출처

ICPC

C++ 메모리 초과 오류 질문 있습니다!

rbstj0311 2년 전 2

amsminn 2년 전 4

rbstj0311 2년 전 4

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말