fork(3) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. struct edge { int to, length; };
  5.  
  6. // The graph used in this example is at 
  7. // https://w...content-available-to-author-only...f.com/IOIPRAC/problems/INOI1402
  8. // You can verify the distance calulated by this program is correct.
  9.  
  10. // Copied Dijsktra code
  11. // Modified it to return a vector of shortest distance to 
  12. // all other nodes from source vertex
  13.  
  14. vector<int> dijkstra2(const vector< vector<edge> > &graph, int source) {
  15.     // ith position in min_distance 
  16.     // stores the minimum distance from source to node i 
  17.     vector<int> min_distance( graph.size(), INT_MAX );
  18.     min_distance[ source ] = 0;
  19.  
  20.     // Active vertices - The vertices whose edges are not yet to be checked 
  21.     set< pair<int,int> > active_vertices;
  22.     active_vertices.insert( {0,source} );
  23.  
  24.     while (!active_vertices.empty()) {
  25.         int where = active_vertices.begin()->second;
  26.         // We don't have any specific target now so it's commented
  27.         // if (where == target) return min_distance[where];
  28.         active_vertices.erase( active_vertices.begin() );
  29.  
  30.         for (auto ed : graph[where])
  31.         	// If new distance is less than the orignal distance 
  32.             if (min_distance[ed.to] > min_distance[where] + ed.length) {
  33.                 active_vertices.erase( { min_distance[ed.to], ed.to } );
  34.  
  35.                 // Stores the shorter distance from source to this vertex 
  36.                 // which just got covered in active_vertices
  37.                 min_distance[ed.to] = min_distance[where] + ed.length;
  38.  
  39.                 // Insert head node of the new edge which just got covered now
  40.                 active_vertices.insert( { min_distance[ed.to], ed.to } );
  41.             }
  42.     }
  43.     return min_distance;
  44. }
  45.  
  46. int main()
  47. {
  48.     ios_base::sync_with_stdio(false);
  49.  
  50.     int n, m, k, tail, head, cost;
  51.     cin >> n >> m;
  52.  
  53.     vector< vector<edge> > graph;
  54.     vector<edge> heads;
  55.  
  56.     for(int i = 0; i < n + 1; i++)
  57.     {
  58.         heads.clear();
  59.         graph.push_back(heads);
  60.     }
  61.  
  62.     for(int i = 0; i < m; i++)
  63.     {
  64.         cin >> tail >> head >> cost;
  65.         edge e;
  66.         e.length = cost;
  67.         e.to = head ;
  68.         graph[tail].push_back(e);
  69.         e.to = tail;
  70.         graph[head].push_back(e);
  71.     }
  72.  
  73.     // The graph used in this example is at 
  74. 	// https://w...content-available-to-author-only...f.com/IOIPRAC/problems/INOI1402
  75. 	// You can verify the distance calulated by this program is correct.
  76.  
  77.     vector<int> dist = dijkstra2(graph, 1);
  78.     for(vector<int>::iterator it = dist.begin()+1; it != dist.end(); it++)
  79.     	// Used begin() + 1 since there is no node 0 in the graph
  80.     	// as begin() would point to 0th index
  81.         cout << "Shortest Distance from 1 to " << it - dist.begin() << " is " << *it << endl;
  82.     return 0;
  83. }
  84.  
  85.  
  86.  
  87.  
  88.  
Success #stdin #stdout 0s 3468KB
comments (?)
stdin
copy 
4 5
1 2 10
1 3 24
2 3 2
2 4 15
3 4 7
stdout
copy 
Shortest Distance from 1 to 1 is 0
Shortest Distance from 1 to 2 is 10
Shortest Distance from 1 to 3 is 12
Shortest Distance from 1 to 4 is 19
https://ideone.com/hq5MsM
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!