글 읽기 - 메모리초과가 발생합니다.

(追記) (追記ここまで)

메모리초과가 발생합니다.

13911번 - 집 구하기

kimtahen 3년 전 0

priority queue를 사용해서 코드를 작성하였는데 메모리 초과가 발생합니다. 이유가 무엇인가요..?

#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <unordered_set>
#include <map>
#include <climits>
#include <cstring>
using namespace std;
#define MAX_NODE 10001
int v, e, mac_num, mac_condition, star_num, star_condition;
unordered_set<int> mac_set, star_set;
struct box{
 int v;
 int w;
};
vector<vector<box>> edge(MAX_NODE, vector<box>()); 
struct Dist{
 int mac_dist = INT_MAX;
 int star_dist = INT_MAX;
};
Dist saved[MAX_NODE]; 
//dijkstra
struct pq_struct{
 int node = -1;
 int dist = INT_MAX;
};
struct cmp{
 bool operator()(pq_struct a, pq_struct b){
 return a.dist > b.dist;
 }
};
int cur_dist[MAX_NODE] = {0,};
int visited[MAX_NODE] = {0,};
void print(){
 for(int i = 1; i<=v; i++){
 cout << "mac_dist: " << saved[i].mac_dist << ", " << "star_dist: " << saved[i].star_dist << endl;
 }
}
int main(){
 //initialize
 scanf("%d %d", &v, &e);
 int u, v, w;
 for(int i = 0; i<e; i++){
 scanf("%d %d %d", &u, &v, &w);
 edge[u].push_back({v, w});
 edge[v].push_back({u, w});
 }
 scanf("%d %d", &mac_num, &mac_condition);
 for(int i = 0; i<mac_num; i++){
 int node;
 scanf("%d",&node);
 mac_set.insert(node);
 }
 scanf("%d %d", &star_num, &star_condition);
 for(int i = 0; i<star_num; i++){
 int node;
 scanf("%d",&node);
 star_set.insert(node);
 }
 int result = INT_MAX;
 priority_queue<pq_struct, vector<pq_struct>, cmp> pq; 
 for(int i = 1; i<=v; i++){
 if(mac_set.find(i)==mac_set.end() && star_set.find(i)==star_set.end()){
 fill(&cur_dist[0], &cur_dist[MAX_NODE], INT_MAX);
 memset(visited, 0, sizeof(visited));
 pq.push({i, 0});
 cur_dist[i] = 0;
 while(!pq.empty()){
 pq_struct target = pq.top();
 pq.pop();
 if(visited[target.node]==1) continue;
 else {
 visited[target.node] = 1;
 
 if(mac_set.find(target.node)!=mac_set.end()){
 saved[i].mac_dist = min(saved[i].mac_dist, target.dist);
 if(saved[i].star_dist != INT_MAX){
 result = min(result, saved[i].mac_dist + saved[i].star_dist); 
 break;
 }
 }
 if(star_set.find(target.node)!=star_set.end()){
 saved[i].star_dist = min(saved[i].star_dist, target.dist);
 if(saved[i].mac_dist != INT_MAX){
 result = min(result, saved[i].mac_dist + saved[i].star_dist); 
 break;
 }
 }
 }
 for(box k: edge[target.node]){
 if(target.dist + k.w < cur_dist[k.v]){
 cur_dist[k.v] = target.dist + k.w;
 pq.push({k.v, target.dist + k.w});
 }
 }
 }
 }
 }
 cout << result;
 
 return 0;
}