fork(6) download
copy 
  1. #include <iostream>
  2. #include<bits/stdc++.h>
  3.  
  4. using namespace std;
  5.  
  6. vector< vector<pair<int,int> > > graph;
  7. vector<int> visited;
  8. vector<int> dist;
  9.  
  10. void Dijkstra(int source,int n)//n is the no. of vertices;
  11. {
  12.     for(int i=1;i<=n;i++)// Initially setting shortest distance of each vertex from the source vertex to be infinity
  13.         dist[i]=INT_MAX;
  14.  
  15.     dist[source]=0;
  16.  
  17.     priority_queue<pair<int,int>, vector<pair<int,int> >,std::greater<pair<int,int> > >p;
  18.     p.push(make_pair(0,source));
  19.  
  20.     while(p.empty()==false)
  21.     {
  22.         pair<int,int> current = p.top();
  23.         p.pop();
  24.         int cv=current.second;//current vertex which has been extracted out from min heap
  25.         int cw=current.first;//current min dist till this vertex from the source
  26.  
  27.         if(visited[cv]==1)//if the node is already visited then continue;
  28.             continue;
  29.  
  30.         visited[cv]=1;//mark the node as visited
  31.  
  32.         for(vector<pair<int,int> >::iterator itr=graph[cv].begin();itr!=graph[cv].end();itr++)
  33.         {
  34.              if(visited[itr->second]==0&&dist[itr->second]>cw+itr->first)
  35.              { dist[itr->second]=cw+itr->first;
  36.              p.push(make_pair(dist[itr->second],itr->second));
  37.  
  38.              }
  39.  
  40.         }
  41.  
  42.     }
  43.  
  44.  
  45.  
  46. }
  47.  
  48. int main()
  49. {
  50.     int n,m,w;
  51.     cin>>n>>m;
  52.  
  53.   graph = vector <vector<pair<int, int> > > (n+1);
  54.   visited = vector<int> (n+1,0);
  55.   dist=vector<int> (n+1);
  56.  
  57.   for(int i=1;i<=m;i++)
  58.   {
  59.       int u,v;
  60.       cin>>u>>v>>w;
  61.       graph[u].push_back(make_pair(w,v));
  62.       graph[v].push_back(make_pair(w,u));
  63.   }
  64.   int source;
  65.   cin>>source;
  66.  
  67.   Dijkstra(source,n);
  68.  
  69.   for(int i=1;i<=n;i++)
  70.     cout<<dist[i]<<" ";
  71.  
  72.  
  73.     return 0;
  74. }
  75.  
Runtime error #stdin #stdout #stderr 0s 4484KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc
https://ideone.com/hUobBy
language:
C++14 (gcc 8.3)
created:
7 years 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!