글 읽기 - 개코전쟁 메모리초과 원인을 모르겠습니다

adxx 3년 전 0

메모리초과를 왜 받는지 모르겠습니다....

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cmath>
typedef long long ll;
using namespace std;

#define fast_cin() ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define pii pair<int,int>
#define vt vector
#define pb push_back
#define X first
#define Y second

#define rep(i, n) for (int i = 0; i < (n); i++)

//int INF = numeric_limits<int>::max();
#define INF 987654321
const int num=1001;
vt<pii> adj[num];
int par[num];
int n,m;
void dij() {
    vector<int> dist(n+1, INF);
    fill(par, par+n+1, -1);dist[1]=0;
    priority_queue<pii> pq;
    pq.push({0, 1});
    while (!pq.empty()) {
        int now = pq.top().Y;
        int cost = -pq.top().X;
        pq.pop();
        for (auto i: adj[now]) {
            int nxt = i.Y;
            int nxtcost = i.X+cost;
            if (nxtcost > dist[nxt]) continue;
            dist[nxt] = nxtcost;
            par[nxt]=now;
            pq.push({-nxtcost, nxt});
        }
    }
}

int dij2(int a, int b) {
    vector<int> dist(n+1, INF);

    priority_queue<pii> pq;
    pq.push({0, 1});dist[1]=0;
    while (!pq.empty()) {
        int now = pq.top().Y;
        int cost = -pq.top().X;
        pq.pop();
        for (auto i: adj[now]) {
            int nxt = i.Y;
            if ((now==a&&nxt==b)||(now==b&&nxt==a)) continue;
            int nxtcost = i.X+cost;
            if (nxtcost > dist[nxt]) continue;
            dist[nxt] = nxtcost;
            pq.push({-nxtcost, nxt});
        }
    }
    return dist[n];
}

int main(void) {
    fast_cin();
    cin >> n >> m;

    rep(i, m) {
        int u,v,w;
        cin >> u >> v >> w;
        adj[u].pb({w, v});
        adj[v].pb({w, u});
    }

    dij();
    int ans=0;
    for(int i=n;;i=par[i]) {
        ans=max(ans, dij2(par[i], i));
        if (par[i]==1) break;
    }
    cout << ans;
    return 0;
}

adxx 3년 전 0

무한루프로 인한 mle

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

문제

문제

출처

ICPC

개코전쟁 메모리초과 원인을 모르겠습니다

adxx 3년 전 0

adxx 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말