fork(11) download
  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
stdin
Standard input is empty
stdout
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"];
}