소프티어

우선 제 풀이는 다음과 같습니다.

1. 데이크스트라를 변형해서 1에서 n까지 가는 경로에 속한 간선들 중 가중치가 가장 큰 간선의 가중치가 가장 작은 경로를 찾습니다.
2. 그 경로에서 가중치가 가장 큰 간선의 가중치보다 큰 가장 작은 소수를 구합니다.

2의 과정을 하는데 있어서 소수들 사이의 간격이 작다는 가정을 세우고 단순 반복문과 루트 시간 소수 판정을 사용해서 데이크스트라 $O((N + M) log N)$ 에 두 소수 사이의 간격의 크기를 $p$ 라고 했을때 총 시간 복잡도 $O((N + M) log N + p \sqrt{10^{9}})$ 정도?되는 풀이를 짠거 같은데 46ms정도로 굉장히 빠르게 통과하더군요. $p$에 비례하는 시간이 걸리는 풀이를 짜도 될 정도로 $p$가 $10^{9}$이하의 소수들에 대해 충분히 작다는게 증명 가능한지 또는 작다라는 정보를 참고할수 있는 출처가 있는지 아니면 틀려야 하는 코드고 데이터가 약한건지 알려주시면 감사하겠습니다.

아래는 제 코드입니다 (정답 스포):

#include <bits/stdc++.h>
using namespace std;


#define endl '\n'


#define PRECISION 12


#define fr first
#define sc second


#define exit ex


using ll = long long;
using ld = long double;


typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef pair<ld, ld>pld;


const ll INF = 1000000000000000;
const ll MOD = 1000000007;


int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};


int n, m;


vector<ll>dp(10005, INF);
bool vis[10005];
vector<pll>edges[10005];


bool isprime(ll k){
    if(k==1) return 0;
    for(ll i=2; i*i<=k; i++){
        if(k%i==0) return 0;
    }
    return 1;
}


void dijk(){
    priority_queue<pll, vector<pll>, greater<pll> >pq;
    dp[1] = 0;
    pq.push({0, 1});
    while(!pq.empty()){
        int cur = pq.top().sc;
        ll w = pq.top().fr;
        pq.pop();
        if(w > dp[cur]) continue;
        for(auto edge:edges[cur]){
            int nxt = edge.sc;
            ll nxtw = edge.fr;
            if(max(nxtw, w)>=dp[nxt]) continue;
            dp[nxt] = max(nxtw, w);
            pq.push({max(nxtw, w), nxt});
        }
    }
}


int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.setf(ios::fixed); cout.precision(PRECISION);


    cin >> n >> m;   


    while(m--){
        int u, v, w;
        cin >> u >> v >> w;
        edges[u].push_back({w, v});
        edges[v].push_back({w, u});
    }


    for(int i=1; i<=n; i++){
        sort(edges[i].begin(), edges[i].end());
    }


    dijk();


    for(ll i=dp[n]+1; i<=1e9+10; i++){
        if(isprime(i)){
            cout << i;
            return 0;
        }
    }
}