fork(13) download
copy 
  1. //./a.out | dot -Tpng >test.png
  2. #include <iostream>
  3. #include <vector>
  4. #include <queue>
  5. #include <algorithm>
  6. using namespace std;
  7.  
  8. struct Edge
  9. {
  10.     int from;
  11.     int to;
  12.     int weight;
  13.     int backPtr;
  14. };
  15. using Edges = vector<Edge>;
  16.  
  17. struct Vertex
  18. {
  19.     vector<int> outEdges;
  20.     int pos = 0;
  21.     int backPtr = -1;
  22. };
  23. using Vertices = vector<Vertex>;
  24.  
  25. struct QEntry
  26. {
  27.     int pathWeight;
  28.     int inEdge;
  29. };
  30. bool operator < (const QEntry& l, const QEntry& r)
  31. {
  32.     return l.pathWeight > r.pathWeight;
  33. }
  34. using PQ = priority_queue<QEntry>;
  35.  
  36. void getDecreasingSP(Vertices& vertices, Edges& edges, int src)
  37. {
  38.     for (auto& v: vertices)
  39.         sort(begin(v.outEdges), end(v.outEdges),
  40.              [&](int from, int to)
  41.              {
  42.                  return edges[from].weight < edges[to].weight;
  43.              });
  44.  
  45.     PQ pq;
  46.     auto& src_v = vertices[src];
  47.     for (auto e: src_v.outEdges)
  48.     {
  49.         QEntry entry {edges[e].weight, e};
  50.         pq.push(entry);
  51.         ++src_v.pos;
  52.     }
  53.  
  54.     while(!pq.empty())
  55.     {
  56.         QEntry top = pq.top();
  57.         pq.pop();
  58.         auto& v = vertices[edges[top.inEdge].to];
  59.  
  60.         while (v.pos < int(v.outEdges.size()) &&
  61.             edges[v.outEdges[v.pos]].weight < edges[top.inEdge].weight)
  62.         {
  63.             auto e = v.outEdges[v.pos];
  64.             edges[e].backPtr = top.inEdge;
  65.             QEntry entry {top.pathWeight + edges[e].weight, e};
  66.             pq.push(entry);
  67.             ++v.pos;
  68.  
  69.             /*cout << edges[top.inEdge].to << " -> "
  70.                 << edges[e].to << " # "
  71.                 << entry.pathWeight << '\n';*/
  72.         }
  73.  
  74.         if (v.backPtr == -1)
  75.             v.backPtr = top.inEdge;
  76.     }
  77. }
  78.  
  79. int main()
  80. {
  81.     Edges edges {
  82.         {0, 1, 1, -1},
  83.         {0, 2, 4, -1},
  84.         {0, 3, 9, -1},
  85.         {1, 2, 2, -1},
  86.         {1, 3, 6, -1},
  87.         {2, 3, 3, -1},
  88.         {3, 4, 4, -1},
  89.         {3, 6, 8, -1},
  90.         {4, 5, 5, -1},
  91.         {5, 3, 7, -1},
  92.         {5, 6, 6, -1},
  93.         {6, 2, 5, -1},
  94.         {6, 7, 7, -1},
  95.         {7, 5, 9, -1},
  96.     };
  97.  
  98.     auto max_from = max_element(begin(edges), end(edges),
  99.                                 [](const Edge& l, const Edge& r) {
  100.                                     return l.from < r.from;
  101.                                 });
  102.  
  103.     auto max_to = max_element(begin(edges), end(edges),
  104.                                 [](const Edge& l, const Edge& r) {
  105.                                     return l.to < r.to;
  106.                                 });
  107.  
  108.     auto max_v = max(max_from->from, max_to->to);
  109.     Vertices vertices(max_v + 1);
  110.     int edge_nr = 0;
  111.  
  112.     for (const auto& e: edges)
  113.         vertices[e.from].outEdges.push_back(edge_nr++);
  114.  
  115.     getDecreasingSP(vertices, edges, 0);
  116.  
  117.     for (auto e = vertices[max_v].backPtr; e >= 0;)
  118.     {
  119.         auto& mark = edges[e].backPtr;
  120.         e = edges[e].backPtr;
  121.         mark = -2;
  122.     }
  123.  
  124.     cout << "digraph test {\n";
  125.     cout << "rankdir=LR;\n";
  126.     cout << "node [label=\"\" shape=circle height=0.1 fillcolor=gray style=filled];\n";
  127.     cout << "edge [label=\"\"];\n";
  128.  
  129.     for (const auto& e: edges)
  130.     {
  131.         cout << 'v' << e.from << " -> v" << e.to << " [label=\"" << e.weight << '"';
  132.         if (e.backPtr == -2)
  133.             cout << " color = red";
  134.         cout << "];\n";
  135.     }
  136.  
  137.     cout << "}\n";
  138. }
  139.  
Success #stdin #stdout 0s 3436KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
digraph test {
rankdir=LR;
node [label="" shape=circle height=0.1 fillcolor=gray style=filled];
edge [label=""];
v0 -> v1 [label="1"];
v0 -> v2 [label="4"];
v0 -> v3 [label="9" color = red];
v1 -> v2 [label="2"];
v1 -> v3 [label="6"];
v2 -> v3 [label="3"];
v3 -> v4 [label="4"];
v3 -> v6 [label="8" color = red];
v4 -> v5 [label="5"];
v5 -> v3 [label="7"];
v5 -> v6 [label="6"];
v6 -> v2 [label="5"];
v6 -> v7 [label="7" color = red];
v7 -> v5 [label="9"];
}
https://ideone.com/8JQ0tB
language:
C++14 (gcc 8.3)
created:
10 years ago
visibility:
secret

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!