소프티어

2, 9, 10, 12 테스트 케이스 오답 나오는데 디버깅이 어렵네요.

그리고 아래 코드입력에서 #include 다 깨져서 안보이는 것 같습니다.

 
#include
#include
#include
#include
#include

#define INT_MAX 1000000001

using namespace std;

int N, M;
unordered_map cost;
vector edges[10000+1];
int memo[10000+1];
bool visited[10000+1];

int traverse(int cur_i){
    if(cur_i == N){
        return 0;
    }
    int &ret = memo[cur_i];
    if(ret != INT_MAX){
        return ret;
    }

    for(auto node: edges[cur_i]){
        if(!visited[node]){
            visited[node] = true;
            int tmp_res = max(traverse(node), cost[cur_i*10001 + node]);
            visited[node] = false;
            if(tmp_res == INT_MAX)
                continue;
            ret = min(ret, tmp_res);
        }
    }
    return ret;
}

int prime(int num){
    bool is_prime = false;
    while(!is_prime){
        is_prime = true;
        int rng = num/2;
        for(int i=2; i<=rng; i++){
            if(num % i == 0){
                is_prime = false;
                break;
            }
        }
        num += 1;
    }

    return max(num-1, 2);
}

int main(int argc, char** argv)
{
    fill_n(memo, 10001, INT_MAX);
    cin >> N >> M;
    for(int i=0; i> s >> d >> c;

        int idx1 = s*10001 + d;
        int idx2 = d*10001 + s;
        if(cost.find(idx1) == cost.end()){
            edges[s].push_back(d);
            edges[d].push_back(s);
            cost[idx1] = c;
            cost[idx2] = c;
        }else{
            cost[idx1] = min(cost[idx1], c);
            cost[idx2] = min(cost[idx2], c);
        }
    }
    visited[1] = true;
    cout << prime(traverse(1)+1) << endl;

    return 0;
}

* 정답코드 수정하여 업데이트 합니다.

#include
#include 
#include 
#include 

#define INT_MAX 1000000001

using namespace std;

int prime(int num){
    bool is_prime = false;
    while(!is_prime){
        is_prime = true;
        int rng = num/2;
        for(int i=2; i<=rng; i++){
            if(num % i == 0){
                is_prime = false;
                break;
            }
        }
        num += 1;
    }

    return num-1;
}

int N, M;

int main(int argc, char** argv)
{
    cin >> N >> M;
    vector>> edges(N+1);
    for(int i=0; i e(3);
        cin >> e[0] >> e[1] >> e[2];
        edges[e[0]].push_back({e[1], e[2]});
        edges[e[1]].push_back({e[0], e[2]});
    }

    vector dist(N+1, INT_MAX);
    auto comp = [](vector& a, vector& b){return a[1] > b[1];};
    priority_queue, vector>, decltype(comp)> pq(comp);
    pq.push({1, 0});
    dist[1] = 0;
    while(!pq.empty()){
        vector nc = pq.top();
        pq.pop();
        if(nc[1] > dist[nc[0]])
            continue;
        for(auto e: edges[nc[0]]){
            if(dist[e[0]] > max(nc[1], e[1])){
                dist[e[0]] = max(nc[1], e[1]);
                pq.push({e[0], dist[e[0]]});
            }
        }
    }

    cout << prime(dist[N]+1) << endl;

    return 0;
}