fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define int long long
  3. using namespace std;
  4. int n,m,d[300005];
  5. vector <int> q[3000006];
  6. vector <pair<int,int>> ve[300005];
  7. void DIAL(int be)
  8. {
  9.     for (int i=1;i<=n;i++) d[i]=1e9;
  10.     d[be]=0,q[0].push_back(be);
  11.     for (int dis=0;dis<=10*(n-1);dis++)
  12.     {
  13.         while (q[dis].size())
  14.         {
  15.             int u=q[dis].back();
  16.             q[dis].pop_back();
  17.             if (d[u]<dis) continue;
  18.             for (pair <int,int> p : ve[u])
  19.             {
  20.                 int v=p.first,w=p.second;
  21.                 if (d[v]>d[u]+w) d[v]=d[u]+w,q[d[v]].push_back(v);
  22.             }
  23.         }
  24.     }
  25.     cout<<d[n];
  26. }
  27. signed main()
  28. {
  29.     ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
  30.     cin>>n>>m;
  31.     for (int i=1;i<=m;i++)
  32.     {
  33.         int u,v,w;
  34.         cin>>u>>v>>w;
  35.         ve[u].push_back({v,w}),ve[v].push_back({u,w});
  36.     }
  37.     DIAL(1);
  38.     return 0;
  39. }
Success #stdin #stdout 0.02s 82724KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/JGYHR0
language:
C++14 (gcc 8.3)
created:
4 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!