Playing On A Directed Graph

YouKnowWho Contest Based on SUST Int...
Limits 1s, 512 MB

You are given a directed graph consisting of nn vertices and mm edges (each edge is directed, so it can be traversed in only one direction). You need to assign a value PiP_i to each vertex ii from 1 to nn so that for each edge uvu→v having weight ww, PvPu  wP_v - P_u ≤ w is satisfied.


The first line contains two integers nn and mm (2n500, 1mmin(n(n1),100000)2 ≤ n ≤ 500, 1 ≤ m ≤ min(n(n - 1), 100000)) — the number of vertices and the number of edges, respectively.

Then mm lines follow. Each line contains three integers uu and vv and ww denoting a directed edge going from vertex uu to vertex vv with weight ww (1u,vn, uv,105  w  1051 ≤ u, v ≤ n, u ≠ v, -10^5 ≤ w ≤ 10^5). Each ordered pair (u,v)(u, v) is listed at most once (there is at most one directed edge from uu to vv).


If there exists any solution print "YES"(without quotes) on the first line. Then on the next line output nn integers where ithi^{th} integer is the value of PiP_i (109  Pi  109-10^9 ≤ P_i ≤ 10^9) i.e. the value assigned to each vertex ii for each ii from 1 to nn. If there are multiple ways to assign values, output any.

If there is no way to assign values to each vertex such that the above conditions are satisfied just print "NO"(without quotes) ending with a new line.

Note that on any line you can't print any trailing space.


4 3
1 2 10
2 3 5
4 2 1
0 0 0 0


Login to submit.


70% Solution Ratio
AnachorEarliest, Dec '19
defaltFastest, 0.0s
defaltLightest, 5.5 kB
Deshi_TouristShortest, 783B
Toph uses cookies. By continuing you agree to our Cookie Policy.