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

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

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

[난이도] level3

[유형] 다익스트라

[풀이]

1에서 출발해서 N까지 도착할때 필요한 최소 레벨을 구하는 문제입니다.

다익스트라를 응용해서 풀 수 있습니다.

일반적인 다익스트라의 경우 [현재 노드 cur 까지 올때까지 필요했던 cost] + [다음 노드 nxt까지 가는데 필요한 cost] 를 더해주어 이 값이 현재 dist[nxt]의 값보다 작다면 이 값으로 dist[nxt]를 업데이트 해주는 방식으로 풀지만

이 문제의 경우 [현재 노드 cur 까지 올때까지 필요한 최소 level]과 [다음 노드 nxt까지 가는데 필요한 level] 의

최댓값과 level[nxt]를 비교해서 업데이트 해주면 됩니다. 왜냐하면 nxt까지 가는데 둘중 더 높은 레벨만큼은 반드시 필요하기 때문입니다.

또한 문제의 조건에 따라 최종노드 N까지 가는데 필요한 level보다 크면서 가장 작은 소수를 구해야 하므로

level[N]보다 큰 첫번째 소수를 구해서 출력해주면 정답이 됩니다.

#include #include #include #include #include using namespace std; int N,M; int level[10001]; vector> 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,vector>,greater>> 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

from http://leesh111112.tistory.com/321 by ccl(A) rewrite - 2021-09-27 21:26:01