CP Lang
26 lineschecks// cco21p4 Travelling Merchant: for each city, the least money that lets you trade forever.
// A city whose roads only lead to dead ends never qualifies; peel those off the reversed graph.
// Then settle answers from the largest requirement down: popping a road's need from a max-heap
// retires it, and the city whose last live road retires has its answer, which raises the need
// of every road into it to max(r, answer - p).
let (n, m) = read<(1..=2e5, 1..=2e5)>()
domain V = 1..=n
domain Road = [m]
let roads = read<[Road](u: V, v: V, r: 0..=1e9, p: 0..=1e9)>()
let doomed = V.mask(Graph.directed(roads).transpose().peel())
let g = Graph.directed(roads).only(v => not doomed[v])
let into = g.transpose()
var left = [V] u => g.deg(u)
var need = Settle<Road, Int>(best: max)
for u in V:
for a in g.out(u):
need.offer(a.e, a.r)
var ans: [V]?Int = None
while let (road, x) = need.pop():
let u = roads[road].u
left[u] -= 1
if left[u] == 0:
ans[u] = x
for a in into.out(u):
need.offer(a.e, max(a.r, x - a.p))
print(ans, none: -1)
Accepted C++
115 lines · 4.43 s on the judge#include "bits/extc++.h"
using namespace std;
template <typename T>
void dbgh(const T& t) {
cerr << t << endl;
}
template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
cerr << t << " | ";
dbgh(u...);
}
#ifdef DEBUG
#define dbg(...) \
cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]" \
<< ": "; \
dbgh(__VA_ARGS__)
#else
#define cerr \
if (false) \
cerr
#define dbg(...)
#endif
#define endl "\n"
#define long int64_t
#define sz(x) int(std::size(x))
struct E {
int u, v, r, p;
};
void solve() {
int n, m;
cin >> n >> m;
vector<E> edges(m);
for (auto& [u, v, r, p] : edges) {
cin >> u >> v >> r >> p;
u--;
v--;
}
bool bad[n] {};
{
int deg[n] {};
vector<int> graph[n];
for (auto& [u, v, _r, _p] : edges) {
deg[u]++;
graph[v].push_back(u);
}
vector<int> q;
auto push = [&](int u) -> void {
if (!deg[u] && !bad[u]) {
bad[u] = true;
q.push_back(u);
}
};
for (int i = 0; i < n; i++) {
push(i);
}
while (sz(q)) {
int u = q.back();
q.pop_back();
for (auto& v : graph[u]) {
deg[v]--;
push(v);
}
}
vector<E> tmp;
for (auto& a : edges) {
if (!bad[a.u] && !bad[a.v]) {
tmp.push_back(a);
}
}
edges = std::move(tmp);
m = sz(edges);
}
int ans[n], deg[n] {};
memset(ans, -1, sizeof(ans));
vector<int> graph[n];
priority_queue<pair<int, int>> pq;
for (int i = 0; i < m; i++) {
deg[edges[i].u]++;
graph[edges[i].v].push_back(i);
pq.emplace(edges[i].r, i);
}
bool vis[m] {};
while (sz(pq)) {
auto [d, i] = pq.top();
pq.pop();
if (vis[i]) {
continue;
}
vis[i] = true;
auto& e = edges[i];
if (!--deg[e.u]) {
ans[e.u] = d;
for (auto& j : graph[e.u]) {
pq.emplace(max(edges[j].r, d - edges[j].p), j);
}
}
}
for (int i = 0; i < n; i++) {
cout << ans[i] << " \n"[i == n - 1];
}
}
int main() {
cin.tie(nullptr);
cin.exceptions(ios::failbit);
ios_base::sync_with_stdio(false);
solve();
}