//./a.out | dot -Tpng >test.png
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
struct Edge
{
int from;
int to;
int weight;
int backPtr;
};
using Edges = vector<Edge>;
struct Vertex
{
vector<int> outEdges;
int pos = 0;
int backPtr = -1;
};
using Vertices = vector<Vertex>;
struct QEntry
{
int pathWeight;
int inEdge;
};
bool operator < (const QEntry& l, const QEntry& r)
{
return l.pathWeight > r.pathWeight;
}
using PQ = priority_queue<QEntry>;
void getDecreasingSP(Vertices& vertices, Edges& edges, int src)
{
for (auto& v: vertices)
sort(begin(v.outEdges), end(v.outEdges),
[&](int from, int to)
{
return edges[from].weight < edges[to].weight;
});
PQ pq;
auto& src_v = vertices[src];
for (auto e: src_v.outEdges)
{
QEntry entry {edges[e].weight, e};
pq.push(entry);
++src_v.pos;
}
while(!pq.empty())
{
QEntry top = pq.top();
pq.pop();
auto& v = vertices[edges[top.inEdge].to];
while (v.pos < int(v.outEdges.size()) &&
edges[v.outEdges[v.pos]].weight < edges[top.inEdge].weight)
{
auto e = v.outEdges[v.pos];
edges[e].backPtr = top.inEdge;
QEntry entry {top.pathWeight + edges[e].weight, e};
pq.push(entry);
++v.pos;
/*cout << edges[top.inEdge].to << " -> "
<< edges[e].to << " # "
<< entry.pathWeight << '\n';*/
}
if (v.backPtr == -1)
v.backPtr = top.inEdge;
}
}
int main()
{
Edges edges {
{0, 1, 1, -1},
{0, 2, 4, -1},
{0, 3, 9, -1},
{1, 2, 2, -1},
{1, 3, 6, -1},
{2, 3, 3, -1},
{3, 4, 4, -1},
{3, 6, 8, -1},
{4, 5, 5, -1},
{5, 3, 7, -1},
{5, 6, 6, -1},
{6, 2, 5, -1},
{6, 7, 7, -1},
{7, 5, 9, -1},
};
auto max_from = max_element(begin(edges), end(edges),
[](const Edge& l, const Edge& r) {
return l.from < r.from;
});
auto max_to = max_element(begin(edges), end(edges),
[](const Edge& l, const Edge& r) {
return l.to < r.to;
});
auto max_v = max(max_from->from, max_to->to);
Vertices vertices(max_v + 1);
int edge_nr = 0;
for (const auto& e: edges)
vertices[e.from].outEdges.push_back(edge_nr++);
getDecreasingSP(vertices, edges, 0);
for (auto e = vertices[max_v].backPtr; e >= 0;)
{
auto& mark = edges[e].backPtr;
e = edges[e].backPtr;
mark = -2;
}
cout << "digraph test {\n";
cout << "rankdir=LR;\n";
cout << "node [label=\"\" shape=circle height=0.1 fillcolor=gray style=filled];\n";
cout << "edge [label=\"\"];\n";
for (const auto& e: edges)
{
cout << 'v' << e.from << " -> v" << e.to << " [label=\"" << e.weight << '"';
if (e.backPtr == -2)
cout << " color = red";
cout << "];\n";
}
cout << "}\n";
}
Ly8uL2Eub3V0IHwgZG90IC1UcG5nID50ZXN0LnBuZwojaW5jbHVkZSA8aW9zdHJlYW0+CiNpbmNsdWRlIDx2ZWN0b3I+CiNpbmNsdWRlIDxxdWV1ZT4KI2luY2x1ZGUgPGFsZ29yaXRobT4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCnN0cnVjdCBFZGdlCnsKICAgIGludCBmcm9tOwogICAgaW50IHRvOwogICAgaW50IHdlaWdodDsKICAgIGludCBiYWNrUHRyOwp9Owp1c2luZyBFZGdlcyA9IHZlY3RvcjxFZGdlPjsKCnN0cnVjdCBWZXJ0ZXgKewogICAgdmVjdG9yPGludD4gb3V0RWRnZXM7CiAgICBpbnQgcG9zID0gMDsKICAgIGludCBiYWNrUHRyID0gLTE7Cn07CnVzaW5nIFZlcnRpY2VzID0gdmVjdG9yPFZlcnRleD47CgpzdHJ1Y3QgUUVudHJ5CnsKICAgIGludCBwYXRoV2VpZ2h0OwogICAgaW50IGluRWRnZTsKfTsKYm9vbCBvcGVyYXRvciA8IChjb25zdCBRRW50cnkmIGwsIGNvbnN0IFFFbnRyeSYgcikKewogICAgcmV0dXJuIGwucGF0aFdlaWdodCA+IHIucGF0aFdlaWdodDsKfQp1c2luZyBQUSA9IHByaW9yaXR5X3F1ZXVlPFFFbnRyeT47Cgp2b2lkIGdldERlY3JlYXNpbmdTUChWZXJ0aWNlcyYgdmVydGljZXMsIEVkZ2VzJiBlZGdlcywgaW50IHNyYykKewogICAgZm9yIChhdXRvJiB2OiB2ZXJ0aWNlcykKICAgICAgICBzb3J0KGJlZ2luKHYub3V0RWRnZXMpLCBlbmQodi5vdXRFZGdlcyksCiAgICAgICAgICAgICBbJl0oaW50IGZyb20sIGludCB0bykKICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICByZXR1cm4gZWRnZXNbZnJvbV0ud2VpZ2h0IDwgZWRnZXNbdG9dLndlaWdodDsKICAgICAgICAgICAgIH0pOwoKICAgIFBRIHBxOwogICAgYXV0byYgc3JjX3YgPSB2ZXJ0aWNlc1tzcmNdOwogICAgZm9yIChhdXRvIGU6IHNyY192Lm91dEVkZ2VzKQogICAgewogICAgICAgIFFFbnRyeSBlbnRyeSB7ZWRnZXNbZV0ud2VpZ2h0LCBlfTsKICAgICAgICBwcS5wdXNoKGVudHJ5KTsKICAgICAgICArK3NyY192LnBvczsKICAgIH0KCiAgICB3aGlsZSghcHEuZW1wdHkoKSkKICAgIHsKICAgICAgICBRRW50cnkgdG9wID0gcHEudG9wKCk7CiAgICAgICAgcHEucG9wKCk7CiAgICAgICAgYXV0byYgdiA9IHZlcnRpY2VzW2VkZ2VzW3RvcC5pbkVkZ2VdLnRvXTsKCiAgICAgICAgd2hpbGUgKHYucG9zIDwgaW50KHYub3V0RWRnZXMuc2l6ZSgpKSAmJgogICAgICAgICAgICBlZGdlc1t2Lm91dEVkZ2VzW3YucG9zXV0ud2VpZ2h0IDwgZWRnZXNbdG9wLmluRWRnZV0ud2VpZ2h0KQogICAgICAgIHsKICAgICAgICAgICAgYXV0byBlID0gdi5vdXRFZGdlc1t2LnBvc107CiAgICAgICAgICAgIGVkZ2VzW2VdLmJhY2tQdHIgPSB0b3AuaW5FZGdlOwogICAgICAgICAgICBRRW50cnkgZW50cnkge3RvcC5wYXRoV2VpZ2h0ICsgZWRnZXNbZV0ud2VpZ2h0LCBlfTsKICAgICAgICAgICAgcHEucHVzaChlbnRyeSk7CiAgICAgICAgICAgICsrdi5wb3M7CgogICAgICAgICAgICAvKmNvdXQgPDwgZWRnZXNbdG9wLmluRWRnZV0udG8gPDwgIiAtPiAiCiAgICAgICAgICAgICAgICA8PCBlZGdlc1tlXS50byA8PCAiICMgIgogICAgICAgICAgICAgICAgPDwgZW50cnkucGF0aFdlaWdodCA8PCAnXG4nOyovCiAgICAgICAgfQoKICAgICAgICBpZiAodi5iYWNrUHRyID09IC0xKQogICAgICAgICAgICB2LmJhY2tQdHIgPSB0b3AuaW5FZGdlOwogICAgfQp9CgppbnQgbWFpbigpCnsKICAgIEVkZ2VzIGVkZ2VzIHsKICAgICAgICB7MCwgMSwgMSwgLTF9LAogICAgICAgIHswLCAyLCA0LCAtMX0sCiAgICAgICAgezAsIDMsIDksIC0xfSwKICAgICAgICB7MSwgMiwgMiwgLTF9LAogICAgICAgIHsxLCAzLCA2LCAtMX0sCiAgICAgICAgezIsIDMsIDMsIC0xfSwKICAgICAgICB7MywgNCwgNCwgLTF9LAogICAgICAgIHszLCA2LCA4LCAtMX0sCiAgICAgICAgezQsIDUsIDUsIC0xfSwKICAgICAgICB7NSwgMywgNywgLTF9LAogICAgICAgIHs1LCA2LCA2LCAtMX0sCiAgICAgICAgezYsIDIsIDUsIC0xfSwKICAgICAgICB7NiwgNywgNywgLTF9LAogICAgICAgIHs3LCA1LCA5LCAtMX0sCiAgICB9OwoKICAgIGF1dG8gbWF4X2Zyb20gPSBtYXhfZWxlbWVudChiZWdpbihlZGdlcyksIGVuZChlZGdlcyksCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgW10oY29uc3QgRWRnZSYgbCwgY29uc3QgRWRnZSYgcikgewogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICByZXR1cm4gbC5mcm9tIDwgci5mcm9tOwogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIH0pOwoKICAgIGF1dG8gbWF4X3RvID0gbWF4X2VsZW1lbnQoYmVnaW4oZWRnZXMpLCBlbmQoZWRnZXMpLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIFtdKGNvbnN0IEVkZ2UmIGwsIGNvbnN0IEVkZ2UmIHIpIHsKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgcmV0dXJuIGwudG8gPCByLnRvOwogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIH0pOwoKICAgIGF1dG8gbWF4X3YgPSBtYXgobWF4X2Zyb20tPmZyb20sIG1heF90by0+dG8pOwogICAgVmVydGljZXMgdmVydGljZXMobWF4X3YgKyAxKTsKICAgIGludCBlZGdlX25yID0gMDsKCiAgICBmb3IgKGNvbnN0IGF1dG8mIGU6IGVkZ2VzKQogICAgICAgIHZlcnRpY2VzW2UuZnJvbV0ub3V0RWRnZXMucHVzaF9iYWNrKGVkZ2VfbnIrKyk7CgogICAgZ2V0RGVjcmVhc2luZ1NQKHZlcnRpY2VzLCBlZGdlcywgMCk7CgogICAgZm9yIChhdXRvIGUgPSB2ZXJ0aWNlc1ttYXhfdl0uYmFja1B0cjsgZSA+PSAwOykKICAgIHsKICAgICAgICBhdXRvJiBtYXJrID0gZWRnZXNbZV0uYmFja1B0cjsKICAgICAgICBlID0gZWRnZXNbZV0uYmFja1B0cjsKICAgICAgICBtYXJrID0gLTI7CiAgICB9CgogICAgY291dCA8PCAiZGlncmFwaCB0ZXN0IHtcbiI7CiAgICBjb3V0IDw8ICJyYW5rZGlyPUxSO1xuIjsKICAgIGNvdXQgPDwgIm5vZGUgW2xhYmVsPVwiXCIgc2hhcGU9Y2lyY2xlIGhlaWdodD0wLjEgZmlsbGNvbG9yPWdyYXkgc3R5bGU9ZmlsbGVkXTtcbiI7CiAgICBjb3V0IDw8ICJlZGdlIFtsYWJlbD1cIlwiXTtcbiI7CgogICAgZm9yIChjb25zdCBhdXRvJiBlOiBlZGdlcykKICAgIHsKICAgICAgICBjb3V0IDw8ICd2JyA8PCBlLmZyb20gPDwgIiAtPiB2IiA8PCBlLnRvIDw8ICIgW2xhYmVsPVwiIiA8PCBlLndlaWdodCA8PCAnIic7CiAgICAgICAgaWYgKGUuYmFja1B0ciA9PSAtMikKICAgICAgICAgICAgY291dCA8PCAiIGNvbG9yID0gcmVkIjsKICAgICAgICBjb3V0IDw8ICJdO1xuIjsKICAgIH0KCiAgICBjb3V0IDw8ICJ9XG4iOwp9Cg==