글 읽기 - 메모리 초과 관련입니다.

vjerksen 7년 전 0

컴파일 시 테스트 케이스는 잘 나오는데, 제출 시 메모리 초과가 발생합니다.

도움 부탁드립니다.

#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<vector>
#include<algorithm>
#include<string.h>
#include<string>
#include<functional>
#include<queue>
#include<stack>
#include<cstring>
#include<cmath>
using namespace std;
#define INF 1<<29
#define MAXX 100010
#define SK 1000000100


// BOJ 1162

int N,M,K;
int u,v,w;
vector<vector<pair<int, int> > > adj;
vector<vector<int> > dist;
priority_queue<pair<pair<int, int>, int > > pq;
void dijkstra(){
    for(int i=1;i<=N;i++){
        for(int j=0;j<=K;j++){
            dist[i][j] = INF;
        }
    }
    for(int i=0;i<=K;i++){
        dist[1][i] = 0;
    }
    pq.push({make_pair(0,1),K});
    while(!pq.empty()){
        int pave = pq.top().second;
        int cost = -pq.top().first.first;
        int here = pq.top().first.second;
        pq.pop();
        for(int i=0;i<adj[here].size();i++){
            int there = adj[here][i].first;
            int nextDist = adj[here][i].second + cost;
            if(pave > 0 && dist[there][pave-1]>cost){
                dist[there][pave-1] = cost;
                pq.push({make_pair(-cost,there),pave-1});
            }
            if(dist[there][pave] > nextDist){
                dist[there][pave] = nextDist;
                pq.push({make_pair(-nextDist,there),pave});

            }

        }
    }
    int ans =INF;
    for(int i=0;i<=K;i++){
        ans = min(ans,dist[N][i]);
    }
    printf("%d",ans);
}
int main(){
    scanf("%d %d %d",&N,&M,&K);
    adj.resize(N+1);
    dist.resize(N+1);
    for(int i=1;i<=N;i++){
        dist[i].resize(N+1);
    }
    for(int i=0;i<M;i++){
        scanf("%d %d %d",&u,&v,&w);
        adj[u].push_back({v,w});
    }
    dijkstra();
    return 0;
}

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

문제

문제

출처

ICPC

메모리 초과 관련입니다.

vjerksen 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말