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. int n, m, k, su[maxn+ 2], sv[maxn+ 2], sw[maxn+ 2];
  16. bool P[maxn+ 2], primes[maxval+ 2];
  17. ll d[5][maxn+ 2], ans;
  18. vector< pair<int, int> > adj[maxn+ 5];
  19.  
  20. void dijkstra(int root, int st) {
  21.     for(int i= 1; i<= n; i++){
  22.         P[i]= false;
  23.         d[root][i]= (ll)1e18;
  24.     }
  25.  
  26.     d[root][st] = 0;
  27.     priority_queue<pair<ll, int> , vector< pair<ll, int> >, greater< pair<ll, int> > > h;
  28.     h.push(make_pair(d[root][st], st));
  29.  
  30.     while(!h.empty()) {
  31.         pair<ll, int> x = h.top();
  32.         h.pop();
  33.  
  34.         int u = x.second;
  35.         if(P[u] == true)    continue;
  36.  
  37.         P[u] = true;
  38.         for(auto e : adj[u]) {
  39.             int v = e.first, w = e.second;
  40.             if(primes[w]== true)    continue;
  41.             if(d[root][v] > d[root][u] + w) {
  42.                 d[root][v] = d[root][u] + w;
  43.                 h.push(make_pair(d[root][v], v));
  44.             }
  45.         }
  46.     }
  47. }
  48.  
  49. int main() {
  50.     ios_base::sync_with_stdio(0);cin.tie(0);
  51.     cin>> n>> m>> k;
  52.     for(int i= 1; i<= m; i++){
  53.         int u, v, w;
  54.         cin>> u>> v>> w;
  55.         adj[u].push_back(make_pair(v, w));
  56.         adj[v].push_back(make_pair(u, w));
  57.         su[i]= u;
  58.         sv[i]= v;
  59.         sw[i]= w;
  60.     }
  61.     for(int i= 1; i<= maxval; i++)  primes[i]= true;
  62.     primes[0] = primes[1] = false;
  63.  
  64.     for (int i = 2; i * i <= maxval; i++) {
  65.         if (primes[i]) {
  66.             for (int j = i * i; j <= maxval; j += i) {
  67.                 primes[j] = false;
  68.             }
  69.         }
  70.     }
  71.     ans= INF;
  72.     dijkstra(0, 1);
  73.     dijkstra(1, n);
  74.     // khong di qua canh nao nguyen to
  75.     ans= min(ans, d[0][n]);
  76.     // di qua 1 canh nguyen to
  77.     for(int i= 1; i<= m; i++){
  78.         ans= min({ans, d[0][su[i]]+ sw[i]+ d[1][sv[i]], d[0][sv[i]]+ sw[i]+ d[1][su[i]]});
  79.     }
  80.     if(ans== INF)   cout<< -1;
  81.     else    cout<< ans;
  82.     return 0;
  83. }
  84.  
Success #stdin #stdout 0.07s 19708KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/WqTzFN
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!