Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Playing On A Directed Graph

By YouKnowWho · Limits 1s, 512 MB · Custom Checker

You are given a directed graph consisting of n vertices and m edges (each edge is directed, so it can be traversed in only one direction). You need to assign a value Pi to each vertex i from 1 to n so that for each edge u→v having weight w, Pv-Pu ≤ w is satisfied.


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

Then m lines follow. Each line contains three integers u and v and w denoting a directed edge going from vertex u to vertex v with weight w  (1 ≤ u, v ≤ n, u ≠ v, -105 ≤ w ≤ 105). Each ordered pair (u, v) is listed at most once (there is at most one directed edge from u to v).


If there exists any solution print "YES"(without quotes) on the first line. Then on the next line output n integers where ith integer is the value of Pi (-109 ≤ Pi ≤ 109 ) i.e. the value assigned to each vertex i for each i from 1 to n. 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



61% Solution Ratio

AnachorEarliest, Dec '19

dip_BRURFastest, 0.0s

AungkurLightest, 1.2 MB

Deshi_TouristShortest, 783B


Login to submit


Coming soon!

Toph uses cookies. By continuing you agree to our Cookie Policy.