[BOJ] 중량제한 - Compy's Blog

중량제한

TimeLimit	MemoryLimit	Condition	TAG
1s	128MB	(2 ≤ N ≤ 10,000, 1 ≤ A, B ≤ N, 1 ≤ C ≤ 1,000,000,000)	BFS

처음 풀이법이 그냥 맞았는데 메모리 초과가 뜸.. 알고보니까 1000인 줄 알았는데 10000이어서 메모리 초과 나는거를 나는 뭐 또 queue에 많이 들어가는 줄 알았네.. ㅠㅜ

또 바꾼 것도 어이가 없긴 하지만 좀 이상하게 풀어버리면서 시간이 좀 걸린 케이스 1시간 컷일 줄 알았는데.. 머 그래도 멀티 테스킹하면서 풀어본 문제라 그렇게 늦게 푼것 같지도 않네요. (사실 bfs 기본 문제라서 오래 걸린게 맞음 ㅠ)

정답 코드


#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <sstream>
#include <iomanip>
#include <string>
#include <numeric>
#include <unordered_set>
#include <unordered_map>
#include <climits>
#include <math.h>
using namespace std;
using ll = long long;
using ld = long double;
ll MOD = 1'000'000'000 + 7;
int inf = 1 << 30;

using namespace std;
int n, m;

int start, finish;


vector<pair<int, int>> nodes[10'001]; // 크기가 1000인줄
int visited[10'001];

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n >> m;
    
    
    for(int i = 1; i <= n; i++){
        visited[i] = 0;
    }
    for(int i = 0; i < m; i++){
        int a, b, c;
        
        cin >> a >> b >> c;
//        cout << a << " " << b << " " << c << "\n";
        // 일단 중복 무시하고 짜보고 걸리면 set으로
        nodes[a].push_back({b, c});
        nodes[b].push_back({a, c});
    
        
    }
    
    
    
    
    cin >> start >> finish;
    
    priority_queue<pair<int, int>> q; // max heap이다
    
    q.push({1'000'000'000, start});
    
    visited[start] =1'000'000'000;
    while(!q.empty()){
        auto [cost, node] = q.top(); q.pop();
        
        if(node == finish) { // 무조건 작아질 수밖에 없는 구조에서 먼저 도착하면 maxheap이므로 그냥 이게 정답
            cout << cost;
            return 0;
        }
        for(pair<int, int> next : nodes[node]){
            
            if(next.second <= 0) continue;
            
            int next_cost = next.second;
//            cout << next_cost << " " << cost << "\n";
            
            if(min(next_cost, cost) > visited[next.first]){
                
                // 아니 처음 접근법이 갸 ㅇ맞았던건데 왜 bool로 바꿨을까 쉬봉방
                visited[next.first] = min(next_cost, cost);
                q.push({min(next_cost, cost), next.first});
                
            }
        }
        
    }
    
    cout << 1;
    

    
    
    return 0;
}