#include <bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;
map<ll, vector<ll>> graph;
ll tolerance;
set<ll> boosterPlacement;
ll weight[500][500] = {-1};
ll dfs(ll node, ll par)
{
if (graph.find(node) == graph.end())
{
return 0;
}
ll d = 0;
for (auto it : graph[node])
{
d = max(weight[node][it] + dfs(it, node), d);
}
if (par != -1 && (d + weight[par][node] > tolerance))
{
boosterPlacement.insert(node);
d = 0;
}
return d;
}
int main()
{
ll u, v, w;
ifstream in("TVSP.txt");
while (in >> u >> v >> w)
{
graph[u].pb(v);
weight[u][v] = w;
}
cout << "Enter Tolerance: ";
cin >> tolerance;
dfs(1, -1);
cout << "Booster Placements: ";
for (auto it : boosterPlacement)
{
cout << it << " ";
}
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CiNkZWZpbmUgbGwgbG9uZyBsb25nCiNkZWZpbmUgcGIgcHVzaF9iYWNrCnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgptYXA8bGwsIHZlY3RvcjxsbD4+IGdyYXBoOwpsbCB0b2xlcmFuY2U7CnNldDxsbD4gYm9vc3RlclBsYWNlbWVudDsKbGwgd2VpZ2h0WzUwMF1bNTAwXSA9IHstMX07CmxsIGRmcyhsbCBub2RlLCBsbCBwYXIpCnsKICAgIGlmIChncmFwaC5maW5kKG5vZGUpID09IGdyYXBoLmVuZCgpKQogICAgewogICAgICAgIHJldHVybiAwOwogICAgfQogICAgbGwgZCA9IDA7CiAgICBmb3IgKGF1dG8gaXQgOiBncmFwaFtub2RlXSkKICAgIHsKICAgICAgICBkID0gbWF4KHdlaWdodFtub2RlXVtpdF0gKyBkZnMoaXQsIG5vZGUpLCBkKTsKICAgIH0KICAgIGlmIChwYXIgIT0gLTEgJiYgKGQgKyB3ZWlnaHRbcGFyXVtub2RlXSA+IHRvbGVyYW5jZSkpCiAgICB7CiAgICAgICAgYm9vc3RlclBsYWNlbWVudC5pbnNlcnQobm9kZSk7CiAgICAgICAgZCA9IDA7CiAgICB9CiAgICByZXR1cm4gZDsKfQppbnQgbWFpbigpCnsKICAgIGxsIHUsIHYsIHc7CiAgICBpZnN0cmVhbSBpbigiVFZTUC50eHQiKTsKICAgIHdoaWxlIChpbiA+PiB1ID4+IHYgPj4gdykKICAgIHsKICAgICAgICBncmFwaFt1XS5wYih2KTsKICAgICAgICB3ZWlnaHRbdV1bdl0gPSB3OwogICAgfQogICAgY291dCA8PCAiRW50ZXIgVG9sZXJhbmNlOiAiOwogICAgY2luID4+IHRvbGVyYW5jZTsKICAgIGRmcygxLCAtMSk7CiAgICBjb3V0IDw8ICJCb29zdGVyIFBsYWNlbWVudHM6ICI7CiAgICBmb3IgKGF1dG8gaXQgOiBib29zdGVyUGxhY2VtZW50KQogICAgewogICAgICAgIGNvdXQgPDwgaXQgPDwgIiAiOwogICAgfQogICAgcmV0dXJuIDA7Cn0K