[Softeer/소프티어][level4] 지우는 소수를 좋아해 (C++)

https://softeer.ai/practice/info.do?eventIdx=1&psProblemId=582&sw_prbl_sbms_sn=16917

Softeer

 

 

[난이도] level4
[유형] 다익스트라

[풀이]
1에서 출발해서 N까지 도착할때 필요한 최소 레벨을 구하는 문제입니다.
다익스트라를 응용해서 풀 수 있습니다.
일반적인 다익스트라의 경우 [현재 노드 cur 까지 올때까지 필요했던 cost] + [다음 노드 nxt까지 가는데 필요한 cost] 를 더해주어 이 값이 현재 dist[nxt]의 값보다 작다면 이 값으로 dist[nxt]를 업데이트 해주는 방식으로 풀지만
이 문제의 경우 [현재 노드 cur 까지 올때까지 필요한 최소 level]과 [다음 노드 nxt까지 가는데 필요한 level] 의
최댓값과 level[nxt]를 비교해서 업데이트 해주면 됩니다. 왜냐하면 nxt까지 가는데 둘중 더 높은 레벨만큼은 반드시 필요하기 때문입니다.

또한 문제의 조건에 따라 최종노드 N까지 가는데 필요한 level보다 크면서 가장 작은 소수를 구해야 하므로
level[N]보다 큰 첫번째 소수를 구해서 출력해주면 정답이 됩니다.

 

#include <cstdio>
#include <queue>
#include <functional>
#include <algorithm>
#include <cmath>
using namespace std;
int N,M;
int level[10001];
vector<pair<int,int>> adj[10001];
int main(){
    scanf("%d%d",&N,&M);
    while(M--){
        int u,v,c;
        scanf("%d%d%d",&u,&v,&c);
        adj[u].push_back({v,c});
        adj[v].push_back({u,c});
    }

    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
    for(int i=1;i<=N;i++) level[i]=1e9;
    pq.push({0,1});
    level[1]=0;

    while(!pq.empty()){
        auto [clv,cur] = pq.top(); pq.pop();
        if(clv!=level[cur]) continue;

        for(auto [nxt,lv] : adj[cur]){
            int nlv = max(lv,clv);
            if(nlv < level[nxt]){
                level[nxt]=nlv;
                pq.push({nlv,nxt});
            }
        }
    }
    for(int i=level[N]+1;;i++){
        bool ok=1;
        for(int j=2;j<=sqrt(i);j++){
            if(i%j==0) {
                ok=0;
                break;
            }
        }
        if(ok) {
            printf("%lld",i);
            return 0;
        }
    }
}

https://github.com/has2/Problem-Solving/blob/master/softeer/level3/지우는_소수를_좋아해.cpp