글 읽기 - 왜 메모리 초과가 날까요...ㅠㅠㅠ

develop_hariff 4년 전 0

DP랑 다익스트라로 짯는데 메모리초과가 4% 5%대에서 납니다ㅠㅠㅠ 도와주세요...

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

typedef long long ll;

ll N, M, L[2501];
ll D[2501][2501], r;
ll x, y, z;

vector<vector<pair<ll, ll>>> v;

int main()
{
    scanf("%lld%lld", &N, &M);
    for(int i = 1; i <= N; i++){
        scanf("%lld", &L[i]);
    }
    v.resize(N + 1);
    for(int i = 0; i < M; i++){
        scanf("%lld%lld%lld", &x, &y, &z);
        v[x].push_back({y, z});
        v[y].push_back({x, z});
    }
    memset(D, -1, sizeof(D));
    priority_queue<pair<ll, pair<ll, ll>>> pq;
    pq.push({0, {1, L[1]}});
    while(!pq.empty()){
        ll now = pq.top().second.first;
        ll cost = -pq.top().first;
        ll minl = pq.top().second.second;
        pq.pop();
        if(D[now][minl] != -1) continue;
        if(now == N){
            r = cost;
            break;
        }
        for(auto i : v[now]){
            if(D[i.first][min(minl, L[i.first])] != -1) continue;
            pq.push({-cost - i.second * minl, {i.first, min(minl, L[i.first])}});
        }
    }
    printf("%lld\n", r);
    return 0;
}

develop_hariff 4년 전 0

ㅋㅋㅋㅋㅋㅋㅋㅋㅋD에 저장을 안했네여ㅠㅠ

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

문제

문제

출처

ICPC

왜 메모리 초과가 날까요...ㅠㅠㅠ

develop_hariff 4년 전 0

develop_hariff 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말