fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define __builtin_popcount __builtin_popcountll
  4. #define BIT(x, i) (((x)>> (i))& (1LL))
  5. #define MASK(x) (1LL<< (x))
  6. #define MOD 1000000007
  7. #define ll long long
  8.  
  9. using namespace std;
  10.  
  11. const int maxm= (int)1e6, maxn= (int)1e5, maxb= (int)1e3, maxval= (int)1e7;
  12.  
  13. ll INF= (ll)1e18;
  14.  
  15. struct Node{
  16.     ll dis;
  17.     int id, cnt;
  18.     Node(ll _dis, int _id, int _cnt){
  19.         dis= _dis;
  20.         id= _id;
  21.         cnt= _cnt;
  22.     }
  23. };
  24.  
  25. struct cmp{
  26.     bool operator () (Node x, Node y){
  27.         return x.dis> y.dis;
  28.     }
  29. };
  30.  
  31. int n, m, k;
  32. bool P[maxn+ 2][10], primes[maxval+ 5];
  33. ll d[maxn+ 2][10], ans;
  34. vector< pair<int, int> > adj[maxn+ 5];
  35.  
  36. void dijkstra(int st) {
  37.     for(int i= 1; i<= n; i++){
  38.         for(int j= 0; j<= k; j++){
  39.             P[i][j]= false;
  40.             d[i][j]= (ll)1e18;
  41.         }
  42.     }
  43.  
  44.     d[st][0] = 0;
  45.     priority_queue<Node , vector<Node>, cmp > h;
  46.     h.push(Node(0, st, 0));
  47.  
  48.     while(!h.empty()) {
  49.         Node x = h.top();
  50.         h.pop();
  51.  
  52.         int u = x.id, state= x.cnt;
  53.         if(P[u][state] == true)    continue;
  54.  
  55.         P[u][state] = true;
  56.         for(auto e : adj[u]) {
  57.             int v = e.first, w = e.second;
  58.             int nstate= state+ primes[w];
  59.             if((nstate<= k)&& (d[v][nstate] > d[u][state] + w)){
  60.                 d[v][nstate] = d[u][state] + w;
  61.                 h.push(Node(d[v][nstate], v, nstate));
  62.             }
  63.         }
  64.     }
  65. }
  66.  
  67. int main() {
  68.     ios_base::sync_with_stdio(0);cin.tie(0);
  69.     cin>> n>> m>> k;
  70.     for(int i= 1; i<= m; i++){
  71.         int u, v, w;
  72.         cin>> u>> v>> w;
  73.         adj[u].push_back(make_pair(v, w));
  74.         adj[v].push_back(make_pair(u, w));
  75.     }
  76.     for(int i= 1; i<= maxval; i++)  primes[i]= true;
  77.     primes[0] = primes[1] = false;
  78.  
  79.     for (int i = 2; i * i <= maxval; i++) {
  80.         if (primes[i]) {
  81.             for (int j = i * i; j <= maxval; j += i) {
  82.                 primes[j] = false;
  83.             }
  84.         }
  85.     }
  86.     ans= INF;
  87.     dijkstra(1);
  88.     for(int i= 0; i<= k; i++){
  89.         ans= min(ans, d[n][i]);
  90.     }
  91.     if(ans== INF)   cout<< -1;
  92.     else    cout<< ans;
  93.     return 0;
  94. }
  95.  
Success #stdin #stdout 0.06s 18332KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/YXVFVP
language:
C++14 (gcc 8.3)
created:
9 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!