fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define ii pair<int,int>
  3. #define st first
  4. #define nd second
  5. using namespace std;
  6.  
  7. const int X=2e5+5;
  8. long long n, m, x, y, d[X], c;
  9. vector<ii>b[X];
  10. priority_queue<ii,vector<ii>,greater<ii> >pq;
  11.  
  12. int main(){
  13.     ios_base::sync_with_stdio(false);   cin.tie(0);
  14.     cin>>n>>m;
  15.     while(m--){
  16.         cin>>x>>y>>c;
  17.         b[x].push_back({c,y});
  18.         b[y].push_back({c,x});
  19.     }
  20.  
  21.     for(int i=1; i<=n; i++) d[i]=1e18;
  22.     d[1]=0;
  23.     pq.push({0,1});
  24.     while(!(pq.empty())){
  25.         ii u=pq.top();
  26.         pq.pop();
  27.         if(d[u.nd]<u.st)    continue;
  28.         for(ii v:b[u.nd]){
  29.             if(d[v.nd]>u.st+v.st){
  30.                 d[v.nd]=u.st+v.st;
  31.                 pq.push({d[v.nd],v.nd});
  32.             }
  33.         }
  34.     }
  35.     cout<<d[n];
  36. }
  37.  
Success #stdin #stdout 0.01s 9360KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/ntjRnO
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!