백준 BOJ 5719 거의 최단 경로

재채점이 되고 메모리초과가 되어있길래

무엇이 문제인지 추측 

 

if (visited[cur_v][next]) continue;

            visited[cur_v][next] = true;

 

위 코드를 추가했더니 통과하였따.

저 부분에 걸리는 테케를 생각해보는데 모르겠다.....

무엇일까

 

 

 

#include<iostream>
#include<memory.h>
#include<vector>
#include<queue>
#include<unordered_map>
#include<algorithm>
#include<string>
#include<cmath>
#define INF 1e9
using namespace std;
using lld = long long int;
using pii = pair<int, int>;
int n, m, k;
vector<pair<int, int>> v[501];
vector<int> trace[501];
 
int dist[501];
bool visited[501][501];
int s, e; // start,end
struct cmp {
    bool operator()(pair<int, int> p1, pair<int, int> p2) {
        return p1.second > p2.second;
    }
};
 
priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> pq;
 
void dijkstra() {
    for (int i = 0; i < n; i++) {
        dist[i] = INF;
    }
    dist[s] = 0;
    pq.push({ s,0 });
    while (!pq.empty()) {
        int cur_v = pq.top().first;
        pq.pop();
 
        for (int i = 0; i < v[cur_v].size(); i++) {
            int next_v = v[cur_v][i].first;
            int cost = v[cur_v][i].second;
 
            if (cost == -1) continue;
            if (dist[cur_v] != INF && dist[next_v] > dist[cur_v] + cost) {
                dist[next_v] = dist[cur_v] + cost;
                pq.push({ next_v , dist[next_v] });
 
                trace[next_v].clear();
                trace[next_v].push_back(cur_v);
            }
 
            else if (dist[cur_v] != INF && dist[next_v] == dist[cur_v] + cost) {
                trace[next_v].push_back(cur_v);
            }
 
        }
    }
}
 
void erase() {
    queue<int> q;
    q.push(e);
    while (!q.empty()) {
        int cur_v = q.front();
        q.pop();
 
        for (int i = 0; i < trace[cur_v].size(); i++) {
            int next = trace[cur_v][i];
            if (visited[cur_v][next]) continue;
            visited[cur_v][next] = true;
 
            for (int j = 0; j < v[next].size(); j++) {
                if (v[next][j].first == cur_v) {       //이전 vertex를 탐색하면서 현재를 가리키는것만 , 현재는 최단경로만 담았기때문에
                    v[next][j].second = -1;
 
                    q.push(next);
                }
            }
        }
    }
}
 
int main() {
    while (1) {
        scanf("%d %d", &n, &m);
        if (n == 0 && m == 0) break;
        for (int i = 0; i < 501; i++) {     //초기화
            v[i].clear();
            trace[i].clear();
        }
        scanf("%d %d", &s, &e);
        for (int i = 0; i < m; i++) {
            int x, y, z;
            scanf("%d %d %d", &x, &y, &z);
            v[x].push_back({ y,z });
        }
        memset(visited, false, sizeof(visited));
 
        dijkstra();
        erase();
        dijkstra();
 
        if (dist[e] == INF) printf("-1\n");
        else printf("%d\n", dist[e]);
 
    }
 
    return 0;
}