PROBLEM LINK:
Author: Jishnu Roychoudhury
Tester: Jatin Yadav
Editorialist: Jishnu Roychoudhury
DIFFICULTY:
Medium-Hard
PREREQUISITES:
Directed Acyclic Graph (DAG), Dynamic Programming (DP), Convex Hull Trick (CHT), Trees, 2^k parent decomposition, Maximum flow
PROBLEM:
There is a directed acyclic graph, where the sole sink is the node 0. For all i, you want to make a journey from node i to node 0. You can travel directly from node u to node v as long as v is reachable from u. The cost of travelling from a node u to a node v is (K-d_v)c_u + t_u. Your journey consists of a sequence of travels. Find the minimum cost of a journey of i to 0, for all i. It is guaranteed that in any set of 11 or more vertices, there will exist at least two vertices u and v, such that it is possible to travel from u to v in the original graph.
Subtask 1 [10 points]: N \leq 1000, M \leq 2000
Subtask 2 [15 points]: M = N-1; u_i=i+1, v_i=i for all i
Subtask 3 [25 points]: M = N-1
Subtask 4 [50 points]: No additional constraints.
QUICK EXPLANATION:
- There is an obvious O(N^2) DP on DAG.
- In the case of a line, the DP can be optimised with CHT.
- By Dilworth’s Theorem, the minimum path cover of the DAG has size at most 10.
- The idea we use is to first find the minimum path cover, and then to run CHT on each of the paths simultaneously.
- If the minimum path cover is of size k, we can find a path cover of size \le klogV with a greedy algorithm.
- We can reduce the path cover to size k by observing that minimum path cover is isomorphic to minimum flow.
- The minimum flow problem can be solved by first finding a feasible flow (with our greedy algorithm) and then subtracting a maximum flow. Ford-Fulkerson works fast because maximum capacity is low.
- We need a persistent CHT. We can maintain this by keeping a tree for our CHT and maintaining a 2^k parent decomposition.
EXPLANATION
Subtask 1
Firstly, we can reverse all edges in the DAG without a real effect on the problem (except reversing our transition vertices). So, we do that, and Rome is now our sole source. The main idea is to run a DP on DAG, starting from Rome. We can precompute whether a path u \rightarrow v exists for all u and v using N depth-first searches. If it does, we create the edge u \rightarrow v in a new graph (so, the new graph is simply the reachability relation of the DAG). Then, we run a single DP on DAG on the new graph (which has O(N^2) edges) and get the answers for all i. Overall complexity is O(N^2). Note that computing d_i for all i in O(N) is a standard DP on DAG.
Also, note that the transition is now dp_v = \min \; (K-d_u)c_v + t_u + dp_u, with transition being the minimum across all u s.t. there is path u \rightarrow v.
Subtask 2
In subtask 1, when we consider node v we are transitioning from all nodes u such that there is a path from u to v. There are at most N nodes to transition from, so it’s O(N^2).
We can optimise this in the case of a line by using CHT. K-d_u is the gradient, t_u + dp_u is the constant, and c_v is the query. In addition, gradients are strictly decreasing, so we can use standard CHT and not worry about Li-Chao tree. Complexity is O(NlogN).
Subtask 3
There are two solutions to the subtask - one is somewhat standard and one that provides the framework for full solution.
Solution 1
We need to adapt our CHT to work on a tree. We can exploit the properties of tree traversal to make this work. The idea is that we maintain our CHT and a stack at each position in order to reverse changes that we made when going down a node. The complexity is O(NlogN).
Since this solution does not contribute to the full solution, we don’t describe it in full detail. For more information, you can read the solution to problem “Harbingers”, from CEOI 2009.
Solution 2
Let’s look at the constraint in the statement regarding how fractured the Roman Empire is. It says that the maximum set of nodes such that all nodes in the set are pairwise unreachable from each other has size 10. In other words, the maximum antichain on the poset which is the reachability relation of the DAG has size 10, and therefore by Dilworth’s Theorem the minimum chain decomposition of the reachability relation of the DAG has size 10.
It can be observed that this is the same as saying that the number of paths in the minimum path cover of the DAG is 10. By “minimum path cover”, we mean a set of paths, such that all vertices appear in at least one path, but could appear in more than one paths.
This is very important since we know how to use CHT on line. We can get the idea that we should first find the minimum path cover, and then run a separate CHT for each path in the minimum path cover. When we reach a vertex v, we first query all of the paths it is on, and then update all of the paths it is on.
For this subtask, it is obvious that we can just create paths from the root to all leaves, since it is a tree. The complexity is O(kNlogN), where k is the size of the minimum path cover. Note that k \leq 10.
Subtask 4
Fine-tuning the Framework
For now let’s just assume that we have a pre-existing minimum path cover. We will describe how to find a minimum path cover later.
Actually, the description of the general method that was given in the explanation of Solution 2 of the previous subtask isn’t completely accurate. The method as described above only works when the minimum path cover contains all edges and some other conditions are satisfied (as it does in the case of a tree) but minimum path cover may not contain all edges, only all vertices.
The key thing is that v should also query paths that v is not on. This is more difficult since if the query is from a path with v, then it can query the minimum from all the transitions before it, but otherwise it may not be able to query all transitions that have already been solved for, it will have to choose some subset.
Fortunately, it is easy to observe that v will only ever have to query some prefix of transitions on a path. If there is a vertex x on path y such that there is a path from x to v, then obviously there is a path from z to v, where z is some vertex occurring before x in the path y. So, we only need to maintain a persistent CHT.
First we have to know what prefixes to query, though. This can actually be precomputed rather simply in O(kN) time with a DP on DAG. We maintain r_{v,i} for all v and i, which is the the prefix of the path i that can reach v (i.e. the prefix v should transition from in path i).
Persistent CHT
We want to maintain a persistent CHT but now we no longer have the properties of tree traversal to help us do it.
When we remove some suffix of transitions and add a new transition, we want to keep the removed transitions to maintain persistence. So the idea is that we can maintain a tree, where the root is an empty CHT, the node x is a transition from x and a path from the root to a node x is the CHT of version x. In other words, the path from the root to x contains the CHT of the prefix ending on node x.
We can do queries and updates using this with 2^k parent decomposition. When we update, set the new node to be the child of the last node that would not be removed from the CHT. When we query, we look for the best element in the path. Both can by maintaining a 2^k parent decomposition for each node.
With this, we have the solution if we know the path cover. The remainder of the problem is to find the path cover.
Greedy Algorithm
We define the following greedy algorithm. Start with no paths, and all nodes unchosen. Then, run a DP which finds the path with the largest amount of unchosen nodes. Choose the nodes on the path, and repeat until all nodes are chosen. This algorithm runs in time complexity O(HM), where H is the number of paths in the retrieved path cover.
In fact, H = O(klogN). Proof below.
Proof
Let’s say we have n remaining uncovered nodes. By Pigeonhole, we can cover at least n / k nodes in our best path, and next iteration there are n(1 - 1/k) remaining to be covered. By now it is somewhat intuitive that this works quite fast. However, we can continue. If H is our number of paths found, then ((k-1)k)^H \le 1 / N. However, note that ((k-1)k)^k \le 1 / e by the Maclaurin series of e^x. So, e^{-H / k} \le 1 / N, and H \le klnN after some rearrangement.
Please note that there are other proofs of this fact, and some are elementary - this one is nice, though.
At this point, we can likely get AC already. Complexity of the solution is O(kM\log N + kN\log^2 N), but constants are extremely favourable. I’m not sure if replacing the CHT described here with a persistent Li-Chao tree would pass, though.
But actually, this isn’t the optimal solution, so we briefly describe that.
Optimal Solution
We can (roughly) observe that there is a duality between path cover and minimum flow. Specifically, any path cover where all paths go from source to a manufactured sink can be converted to a minimum flow, and vice versa. Note that “demand” in min flow can only be a property of edges, so duplicate each vertex v into two edges, v_{in} and v_{out}, where v_{in} stores has all incoming edges to v, v_{out} has all outcoming edges, and there is an edge v_{in} \rightarrow v_{out} with demand 1. All other edges have demand 0.
To solve the minimum flow problem, one way is to first find a feasible flow and then to subtract a maximum flow on the capacities (the excess). To find the feasible flow, we can use the greedy algorithm before on our slightly modified graph. This provides a flow with maximum capacity \approx klnN. To reduce the flow, we can use Ford-Fulkerson, which runs in time O(E \cdot f_{max}) where f_{max} is the maximum flow capacity if flows are integral. Note that when running maximum flow, the capacity of the edge e should be f_e - d_e where f_e is the number of edges passing through e in the feasible path cover/value of feasible flow and d_e is demand. Finally, our final minimum flow is f_e - g_e for edge e, where g_e is the returned value of max flow on the edge.
The time complexity of this solution is O(kM\log N + kN\log N).
SOLUTIONS:
Setter's Solution
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
const int N=1e5+5e4,M=2e5+5e4;
int n,m;
ll t[N],k; //Note: Tax is variable.
ll c[N];
namespace LogGreed{
vector<int> g[2*N]; //vin vout
vector<int> g_inc[2*N];
vector<vector<int> > paths;
vector<int> topo_g;
bool topo_vis[2*N];
int req[2*N];
void toposort(int x){ //TopoSort
if(topo_vis[x]) return;
topo_vis[x] = 1;
for(int i : g[x]){
toposort(i);
}
topo_g.push_back(x);
}
void bigloop(){ //While loop for greedy algorithm
int lp[n+n+5],bef[n+n+5];
while(true){
memset(lp,0,sizeof(lp));
memset(bef,-1,sizeof(bef));
for(int v : topo_g){ //create longestpath array
lp[v] = req[v];
for(int k : g_inc[v]){
if(req[v]+lp[k] >= lp[v]){
bef[v]=k;
lp[v]=req[v]+lp[k];
}
}
}
int mxn=2*n;
vector<int> newPath;
while(mxn!=-1){
newPath.push_back(mxn);
req[mxn]=0;
mxn=bef[mxn];
}
//for(int i : newPath) cout<<i<<endl;
//for(int i=0; i<=n+n; i++) <<req[i]<<' ';
reverse(newPath.begin(),newPath.end());
paths.push_back(newPath);
int sm=0;
for(int i=0; i<=n+n; i++) sm+=req[i];
if(sm==0) return;
}
}
void greedy_cover(){ //Find greedy cover
for(int i=0; i<=(2*n); i++) req[i] = 1;
//cout<<"BIGLOOP"<<endl;
bigloop();
}
void greed(){ //"Main" of LogGreed
//cout<<"LOGGREED"<<endl;
toposort(0); //start from Rome
//cout<<"TOPOSORT"<<endl;
reverse(topo_g.begin(),topo_g.end());
greedy_cover();
//cout<<"GREEDYCOVER"<<endl;
}
}
namespace MxFlow{
unordered_map<int,int> graph[2*N];
int source,sink;
int num_paths;
void createFlow(){
for(int i=0; i<LogGreed::paths.size(); i++){
for(int j=0; j<LogGreed::paths[i].size()-1; j++){
int u=LogGreed::paths[i][j],v=LogGreed::paths[i][j+1];
if(!graph[u].count(v)){ graph[u].insert({v,1}); graph[v].insert({u,0});}
else graph[u][v]++; //created 0-cap edges also
}
} //forward edges
for(int u=0; u<n; u++){
graph[u][u+n]--; //d(e)=1
}
}
int edmondsKarp(){ //KACTL Edmonds-Karp
int flow=0;
vector<int> par(n+n+5), q=par;
for(;;){
fill(par.begin(),par.end(),-1);
par[source]=0;
int ptr=1;
q[0]=source;
for(int i=0; i<ptr; i++){
int x=q[i];
for(auto e : graph[x]){
if(par[e.first]==-1&&e.second>0){
par[e.first]=x;
q[ptr++] = e.first;
if(e.first==sink) goto out;
}
}
}
//ending sequence here
return flow;
out :
int inc = 1e9+15;
for(int y=sink; y!=source; y=par[y])
inc = min(inc,graph[par[y]][y]);
flow+=inc;
//cout<<flow<<endl;
for(int y=sink; y!=source; y=par[y]){
int p=par[y];
if((graph[p][y]-=inc)<=0) graph[p].erase(y);
graph[y][p]+=inc;
}
}
}
void maxFlow(){
//cout<<"MAXFLOW"<<endl;
source=0; sink=n+n;
createFlow();
num_paths = edmondsKarp();
num_paths = graph[0][n] + 1;
//cout<<"NP"<<num_paths<<endl;
}
}
namespace StdGraph{
vector<pair<int,ll> > adj[N]; //adj list
vector<pair<int,ll> > adj_inc[N]; //incoming to node
vector<pair<int,int> > flo[N]; //out, flow
vector<vector<int> > paths;
bool topo_vis[N];
vector<int> topo;
void getFlows(){ //get flows from mxflow
for(int i=0; i<n; i++){
for(auto j : adj[i]){
int u=i+n, v=j.first;
if(MxFlow::graph[u].count(v)){
flo[i].push_back({v,MxFlow::graph[u][v]});
}
else flo[i].push_back({v,0});
}
}
}
void toposort(int x){
if(topo_vis[x]) return;
topo_vis[x]=1;
for(auto i : adj[x]){
toposort(i.first);
}
topo.push_back(x);
}
void getPaths(){
int np = MxFlow::num_paths;
for(int i=0; i<np; i++){ //put 0 at the start of every path
vector<int> new_path; new_path.push_back(0);
paths.push_back(new_path);
}
toposort(0);
reverse(topo.begin(),topo.end());
for(int u : topo){ //create paths
int cr=0;
for(auto k : flo[u]){ //go through adjacents
int v=k.first, val=k.second;
if(val==0) continue;
while(val--){
while(paths[cr].back()!=u) cr++; //infinite loop if Maxflow bad
paths[cr].push_back(v); //append to paths
cr++;
}
}
}
}
void constructPathCover(){
//cout<<"STDGRAPH"<<endl;
getFlows();
//cout<<"GETFLOWS"<<endl;
getPaths();
//for(int i : paths[0]) cout<<i<<' ';
//cout<<endl;
}
}
struct node{
ll m,c;
};
struct CHT{
int p[N][20];
node lines[N];
int lst;
CHT(){
memset(p,-1,sizeof(p));
}
ll value(int pos, ll xval){
return (lines[pos].m * xval) + lines[pos].c;
}
long double intersect(ll m1, ll c1, ll m2, ll c2){
return (long double)(c2-c1)/(long double)(m1-m2);
}
long double intersect(node a, node b){
return intersect(a.m,a.c,b.m,b.c);
}
ll qry(ll inte, int x){
int y = x;
for(int i=19; i>=0; i--){
if(p[x][i] == -1 || p[p[x][i]][0]==-1) continue;
if(value(p[x][i],inte) > value(p[p[x][i]][0],inte)){
x = p[x][i];
}
}
while(p[x][0]!=-1&&value(x,inte) > value(p[x][0],inte)) x=p[x][0];
return value(x,inte);
}
void add(int x, ll grad, ll con){
lines[x].m=grad; lines[x].c=con;
int add_to = lst;
for(int i=19; i>=0; i--){
int u = p[add_to][i]; if(u==-1) continue;
if(p[u][0]==-1) continue;
if(intersect(lines[u],lines[x]) <= intersect(lines[p[u][0]],lines[x])){ //removal
add_to = u;
}
}
while(p[add_to][0]!=-1&&intersect(lines[add_to],lines[x]) <= intersect(lines[p[add_to][0]],lines[x])){
add_to = p[add_to][0];
}
p[x][0] = add_to;
for(int k=1; k<20; k++){
if(p[x][k-1] != -1){
p[x][k] = p[p[x][k-1]][k-1];
} else p[x][k] = -1;
}
}
} *chains[120];
namespace DynaProgram{
ll d[N]; //Danger values
int reach[N][120]; //last2reach
int pos_best[N][120]; //max(last2reach,self)
ll dp[N]; //dp vals
int path_numb[N][120]; //number on each path
void dagDP(){ //DP for Danger values
memset(d,0,sizeof(d));
for(int v : StdGraph::topo){
for(auto k : StdGraph::adj_inc[v]){
d[v] = max(d[v],d[k.first]+k.second);
}
}
}
void pathnumbering(){
memset(path_numb,-1,sizeof(path_numb));
for(int i=0; i<MxFlow::num_paths; i++){
for(int j=0; j<StdGraph::paths[i].size(); j++){
int v = StdGraph::paths[i][j];
path_numb[v][i] = j;
}
}
}
void reachability(){ //Reachability queries in O(1)
pathnumbering();
memset(reach,0,sizeof(reach));
memset(pos_best,0,sizeof(pos_best));
//gotta find a path numbering LOL
for(int v : StdGraph::topo){
int mxp[120]; memset(mxp,-1,sizeof(mxp));
for(auto k : StdGraph::adj_inc[v]){
int u=k.first;
for(int i=0; i<MxFlow::num_paths; i++){
if(path_numb[pos_best[u][i]][i] > mxp[i]){ //if path numb better than best
reach[v][i] = pos_best[u][i];
mxp[i] = path_numb[pos_best[u][i]][i];
}
}
}
for(int i=0; i<MxFlow::num_paths; i++){
pos_best[v][i] = reach[v][i];
if(path_numb[v][i] > path_numb[pos_best[v][i]][i]){
pos_best[v][i] = v;
}
}
}
}
void initCHT(){ //Initialise CHT
for(int i=0; i<MxFlow::num_paths; i++){
chains[i] = new CHT();
//chains[i]->add(0,k,t[0]);
chains[i]->lines[0].m = k;
chains[i]->lines[0].c = t[0];
chains[i]->lst = 0;
}
}
void finDP(){ //final DP for values
dp[0]=0;
for(int v : StdGraph::topo){
if(v==0) continue;
//cout<<"V"<<v<<endl;
//query chains
ll min_Dp=6e18;
for(int i=0; i<MxFlow::num_paths; i++){
min_Dp = min(min_Dp,chains[i]->qry(c[v],reach[v][i]));
}
//cout<<"QRY"<<endl;
dp[v] = min_Dp;
//insert chain
for(int i=0; i<MxFlow::num_paths; i++){
if(path_numb[v][i]!=-1){
//cout<<"ADDENTER"<<endl;
chains[i]->add(v,k-d[v],dp[v]+t[v]);
//cout<<"ADDEXIT"<<endl;
chains[i]->lst = v;
}
}
//cout<<"NUMPATHS"<<endl;
}
}
void entry(){
//cout<<"DYNAPROGRAM"<<endl;
dagDP();
//cout<<"DAGDP"<<endl;
reachability();
//cout<<"REACHABILITY"<<endl;
initCHT();
//cout<<"INITCHT"<<endl;
finDP();
//cout<<"FINDP"<<endl;
}
}
unordered_set<int> conn[N];
void inp(){
cin>>n>>m>>k;
for(int i=0; i<n; i++) cin>>c[i];
for(int i=0; i<n; i++) cin>>t[i];
for(int i=0; i<m; i++){
int u,v; ll w;
cin>>v>>u>>w;
StdGraph::adj[u].push_back({v,w});
StdGraph::adj_inc[v].push_back({u,w});
LogGreed::g[u+n].push_back(v); //add uout->vin
conn[u].insert(v);
}
for(int i=0; i<n; i++){ //add vin->vout
LogGreed::g[i].push_back(i+n);
}
for(int i=n; i<n+n; i++){ //add sink
if(LogGreed::g[i].empty()) LogGreed::g[i].push_back(n+n);
}
for(int i=0; i<=n+n; i++){ //create g_inc
for(int j : LogGreed::g[i]){
LogGreed::g_inc[j].push_back(i);
}
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
inp(); //input
LogGreed::greed(); //greedy path cover klogV
MxFlow::maxFlow(); //maxflow
//cout<<MxFlow::num_paths<<endl;
if(MxFlow::num_paths > 120) exit(64);
StdGraph::constructPathCover(); //get path cover from maxflow
DynaProgram::entry();
for(int i=1; i<n; i++) assert(DynaProgram::dp[i] >= 0);
for(int i=1; i<n; i++) cout<<DynaProgram::dp[i]<<' ';
bool have_done[N]; memset(have_done,0,sizeof(have_done));
for(int i=0; i<MxFlow::num_paths; i++){
for(int j=0; j<StdGraph::paths[i].size()-1; j++){
int u = StdGraph::paths[i][j], v=StdGraph::paths[i][j+1];
if(conn[u].find(v)==conn[u].end()) exit(404);
have_done[u]=1; have_done[v] = 1;
}
}
for(int i=0; i<n; i++){
if(!have_done[i]) exit(304);
}
//cout<<endl; cout<<DynaProgram::reach[2][0];
}
Tester's Solution
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define F first
#define S second
#define all(c) ((c).begin()), ((c).end())
#define sz(x) ((int)(x).size())
#define ld long double
template<class T,class U>
ostream& operator<<(ostream& os,const pair<T,U>& p){
os<<"("<<p.first<<", "<<p.second<<")";
return os;
}
template<class T>
ostream& operator <<(ostream& os,const vector<T>& v){
os<<"{";
for(int i = 0;i < (int)v.size(); i++){
if(i)os<<", ";
os<<v[i];
}
os<<"}";
return os;
}
#ifdef LOCAL
#define cerr cout
#else
#endif
#define TRACE
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif
long long readInt(long long l,long long r,char endd){
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true){
char g=getchar();
if(g=='-'){
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g && g<='9'){
x*=10;
x+=g-'0';
if(cnt==0){
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);
assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd){
if(is_neg){
x= -x;
}
if(!(l<=x && x<=r))cerr<<l<<"<="<<x<<"<="<<r<<endl;
assert(l<=x && x<=r);
return x;
} else {
assert(false);
}
}
}
string readString(int l,int r,char endd){
string ret="";
int cnt=0;
while(true){
char g=getchar();
assert(g!=-1);
if(g==endd){
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt && cnt<=r);
return ret;
}
long long readIntSp(long long l,long long r){
return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
return readString(l,r,'\n');
}
string readStringSp(int l,int r){
return readString(l,r,' ');
}
template<class T>
vector<T> readVector(int n, long long l, long long r){
vector<T> ret(n);
for(int i = 0; i < n; i++){
ret[i] = i == n - 1 ? readIntLn(l, r) : readIntSp(l, r);
}
return ret;
}
const int INF = 1e9;
const ll INF_LL = 1LL << 60;
struct graph{
vector<vector<int>> adj;
vector<int> mate;
int n;
graph(int n) : n(n), adj(n), mate(n + n, -1){};
void add_edge(int u, int v){
adj[u].push_back(v);
}
void max_matching(){
vector<int> vis(n), vis2(n);
vector<int> reachable;
function<void(int)> rec = [&](int u){
reachable.push_back(u + n);
vis2[u] = 1;
for(int v : adj[u]) if(!vis2[v]) rec(v);
};
function<vector<int>(int)> get = [&](int x){
reachable.clear();
for(int u : adj[x]) if(!vis2[u]) rec(u);
return reachable;
};
function<bool(int)> augment = [&](int u) {
vis[u] = true;
for (int w: get(u)) {
if(w == mate[u]) continue;
int v = mate[w];
if (v < 0 || (!vis[v] && augment(v))) {
mate[u] = w;
mate[w] = u;
return true;
}
}
return false;
};
while(true){
int increased = false;
fill(all(vis), 0);
fill(all(vis2), 0);
for(int u = 0; u < n; u++) if(mate[u] == -1 && augment(u)){
increased = true;
break;
}
if(!increased) return;
}
}
};
typedef long long Long;
struct Line {
Long a, b, get(Long x) { return a * x + b; }
};
struct ConvexHull {
int size;
Line *hull;
ConvexHull(){}
ConvexHull(int maxSize) {
hull = new Line[++maxSize], size = 0;
}
bool is_bad(int curr, int prev, int next) {
Line c = hull[curr], p = hull[prev], n = hull[next];
return (c.b - n.b) * __int128_t(c.a - p.a) <= (p.b - c.b) * __int128_t(n.a - c.a);
}
void add_line(Long a, Long b) {
hull[size++] = (Line){a, b};
while (size > 2 && is_bad(size - 2, size - 3, size - 1))
hull[size - 2] = hull[size - 1], size--;
}
Long query(Long x) {
int l = -1, r = size - 1;
while (r - l > 1) {
int m = (l + r) / 2;
if (hull[m].get(x) <= hull[m + 1].get(x))
l = m;
else
r = m;
}
return hull[r].get(x);
}
};
int main(){
int n = readIntSp(2, 100000), m = readIntSp(1, 200000), K = readIntLn(1, INF);
vector<int> c = readVector<int>(n, 1, INF), t = readVector<int>(n, 1, INF), indeg(n), pos(n);
graph G(n);
vector<vector<pair<int, int>>> ADJ(n);
for(int i = 0; i < m; i++){
int u = readIntSp(0, n - 1), v = readIntSp(0, n - 1), w = readIntLn(1, 10000);
G.add_edge(u, v);
ADJ[u].push_back({v, w});
indeg[v]++;
}
vector<int> V;
for(int i = 0; i < n; i++) if(indeg[i] == 0) V.push_back(i);
vector<int> nodes;
while(!V.empty()){
int u = V.back(); V.pop_back();
pos[u] = n - 1 - nodes.size();
nodes.push_back(u);
for(int v : G.adj[u]){
indeg[v]--;
if(indeg[v] == 0){
V.push_back(v);
}
}
}
vector<int> vis(n);
vector<int> rev_nodes = nodes;
reverse(all(nodes));
for(int i = 0; i < n; i++) sort(all(G.adj[i]), [&](int u, int v){return pos[u] > pos[v];});
int num = 0;
while(accumulate(all(vis), 0) < n){
num++;
vector<int> dp(n);
vector<int> prv(n);
int best = -1;
for(int x : nodes){
prv[x] = x;
dp[x] = !vis[x];
for(int y : G.adj[x]){
assert(pos[y] < pos[x]);
int L = dp[y] + !vis[x];
if(L > dp[x]){
dp[x] = L;
prv[x] = y;
}
}
if(best == -1 || dp[x] > dp[best]) best = x;
}
while(prv[best] != best){
vis[best] = 1;
int P = best;
while(vis[P]) P = prv[P];
G.mate[best] = P + n;
G.mate[P + n] = best;
best = P;
}
vis[best] = 1;
}
G.max_matching();
vector<vector<int>> paths;
vector<int> path;
function<bool(int, int)> getPath = [&](int x, int y){
vis[x] = 1;
if(x == y){
path.push_back(y);
return true;
}
for(int v : G.adj[x]){
if(pos[v] < pos[y]) return false;
if(vis[v]) continue;
if(getPath(v, y)){
path.push_back(x);
return true;
}
}
return false;
};
vector<vector<int>> mx(10, vector<int>(n, -1));
vector<vector<int>> where = mx;
vector<vector<vector<int>>> inv_mx(10, vector<vector<int>>(n));
vector<int> L(n);
for(int v : rev_nodes) if(G.mate[v + n] == -1){
fill(all(vis), 0);
path.clear();
path.push_back(v);
while(G.mate[v] != -1){
int y = G.mate[v] - n;
int position = path.size();
getPath(v, y);
path.pop_back();
reverse(path.begin() + position, path.end());
v = y;
}
reverse(all(path));
for(int i = 0; i < path.size(); i++){
where[paths.size()][path[i]] = i;
}
paths.push_back(path);
}
int k = paths.size();
assert(k <= 10);
for(int u : nodes){
for(auto it : ADJ[u]){
int v = it.first;
L[u] = max(L[u], L[v] + it.second);
for(int j = 0; j < k; j++) mx[j][u] = max(mx[j][u], mx[j][v]);
}
for(int i = 0; i < k; i++){
if(mx[i][u] != -1) inv_mx[i][mx[i][u]].push_back(u);
mx[i][u] = max(mx[i][u], where[i][u]);
}
}
vector<ll> dp(n, INF_LL);
dp[0] = 0;
vector<ConvexHull> cht(k);
for(int i = 0; i < k; i++) cht[i] = ConvexHull(paths[i].size());
for(int u : nodes){
int covered = 0;
for(int i = 0; i < k; i++){
int pos = where[i][u];
if(pos != -1){
covered = 1;
cht[i].add_line(L[u] - K, - t[u] - dp[u]);
for(int v : inv_mx[i][pos]){
dp[v] = min(dp[v], -cht[i].query(c[v]));
}
}
}
assert(covered);
}
for(int i = 1; i < n; i++){
assert(dp[i] != INF_LL);
printf("%lld ", dp[i]);
}
printf("\n");
assert(getchar()==-1);
}