fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define int long long
  3. #define fast ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
  4. #define lg2(n) (63-__builtin_clzll(n))
  5. #define mask(n) (1LL << (n))
  6. #define TASK ""
  7. #define openfile();  if( fopen(TASK".inp", "r")){freopen(TASK".inp", "r", stdin);freopen(TASK".out", "w", stdout);}
  8. #define lc(n) (n << 1)
  9. #define rc(n) ((n << 1) | 1)
  10.  
  11. #define fi first
  12. #define se second
  13. #define FOR(i, l, r, k) for( int i = l; i <= r; i += k)
  14. #define FOD(i, r, l, k) for( int i = r; i >= l; i -= k)
  15.  
  16. #define mii map<int,int>
  17. #define umi unordered_map<int, int>
  18. #define pii pair<int,int>
  19. #define vi vector<int>
  20.  
  21. using namespace std;
  22.  
  23. const int oo = 1e18;
  24. const int mod = 1e9 + 7;
  25. const int nmax = 2e5 + 8;
  26. const int base = 31;
  27.  
  28. int n, m, dis[nmax], dis2[nmax];
  29. vector<pii> g[nmax];
  30.  
  31. void dijkstra(int u){
  32.     priority_queue<pii, vector<pii>, greater<pii>> pq;
  33.     pq.push({0, u});
  34.     dis[u] = 0;
  35.     while(!pq.empty()){
  36.         auto top = pq.top(); pq.pop();
  37.         if(top.fi > dis2[top.se]) continue;
  38.         for(auto &x : g[top.se]){
  39.             int val = top.fi + x.fi;
  40.             if(val < dis[x.se]){
  41.                 pq.push({val, x.se});
  42.                 swap(dis[x.se], dis2[x.se]);
  43.                 dis[x.se] = val;
  44.             }
  45.             if(val < dis2[x.se] && val > dis[x.se]){
  46.                 pq.push({val, x.se});
  47.                 swap(val, dis2[x.se]);
  48.             }
  49.         }
  50.     }
  51. }
  52.  
  53. main(){
  54.     fast;
  55.     openfile();
  56.     cin >> n >> m;
  57.     for(int i = 1; i <= m; ++i){
  58.         int u, v, w;
  59.         cin >> u >> v >> w;
  60.         g[u].push_back({w, v});
  61.         g[v].push_back({w, u});
  62.     }
  63.     memset(dis, 0x3f, sizeof dis);
  64.     memset(dis2, 0x3f, sizeof dis2);
  65.     dijkstra(1);
  66.     cout << dis2[n];
  67. }
  68.  
Success #stdin #stdout 0.01s 11440KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
4557430888798830399
https://ideone.com/0v6ozU
language:
C++14 (gcc 8.3)
created:
2 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!