Pranzo Delizioso#10399
Le mucche stanno tornando alla stalla alla fine di una lunga giornata, sentendosi sia stanche che affamate.
La fattoria è composta da pascoli, numerati convenientemente da a . Tutte le mucche vogliono raggiungere la stalla, che si trova nel pascolo . Ciascuno degli altri n - 1 pascoli contiene una mucca. Le mucche possono spostarsi tra i pascoli lungo sentieri non orientati. Il sentiero -esimo collega i pascoli a_i e b_i e richiede un tempo t_i per essere percorso. Ogni mucca può raggiungere la stalla tramite una qualche sequenza di sentieri.
Essendo affamate, le mucche vorrebbero fermarsi per uno spuntino durante il tragitto verso casa. Fortunatamente, pascoli contengono gustose balle di fieno, e la -esima balla di fieno ha un valore di gusto pari a y_i. Ogni mucca è disposta a fermarsi presso una balla di fieno durante il tragitto verso la stalla, ma solo se questo aumenta il suo tempo di viaggio, rispetto al percorso più breve verso la stalla, di al massimo il valore di gusto della balla che visita. Si noti che una mucca visita "ufficialmente" al massimo una balla di fieno per mangiare; va bene se il suo percorso attraversa altri pascoli con balle di fieno — semplicemente li ignora.
Per ogni mucca, determinare se può fermarsi presso una balla di fieno durante il tragitto verso la stalla.
La prima riga contiene tre interi , e k~(2 \le n \le 5 \cdot 10^4, 1 \le m \le 10^5, 1 \le k \le n). Ciascuna delle successive righe contiene tre interi a_i, b_i e t_i~(a_i \ne b_i, 1 \le t_i \le 10^4), che descrivono un sentiero tra i pascoli a_i e b_i che richiede un tempo t_i per essere percorso.
Ciascuna delle successive righe descrive una balla di fieno e contiene due interi: il numero del pascolo in cui si trova e il suo valore di gusto y_i~(1 \le y_i \le 10^9). Più balle di fieno possono trovarsi nello stesso pascolo.
Stampare n - 1 righe. La riga -esima deve contenere se la mucca nel pascolo può fermarsi a mangiare presso una balla di fieno durante il tragitto verso la stalla, e altrimenti.
Esempio 1
In questo esempio, la mucca nel pascolo dovrebbe fermarsi per un pasto, poiché il suo tempo di viaggio aumenta solo di (da a ), il che non supera il valore di gusto della balla di fieno. La mucca nel pascolo dovrebbe ovviamente mangiare il fieno nel pascolo , poiché ciò non cambia affatto il suo percorso ottimale. La mucca nel pascolo è un caso interessante: a prima vista, potrebbe sembrare che il suo percorso ottimale (di lunghezza ) aumenterebbe troppo per rendere conveniente la sosta. Tuttavia, esiste un percorso che rende conveniente fermarsi per il fieno: andare al pascolo , poi al pascolo (dove mangia il fieno), e poi tornare al pascolo .