The opposite happened to me. I registered for the Regular contest and couldn't go to the Beginner contest anymore. xD. But, I was able to solve problem C. Was this an easier C than usual AtCoder contests ?

Idea: use BFS and push nodes with indegree 0 first. Then, update distances for each node reachable from source (like multi source shortest path). Check while updating data for any contradiction.

My AC Submission: https://abc087.contest.atcoder.jp/submissions/2034615

no. You could have something like this:

A->B 5 B->C 3 A->C 100

which contradicts itself. (distance between AC != AC + BC)

If the graph is not a DAG, answer is definitely "NO". If the graph is a DAG, it is NOT guaranteed that the answer is "YES".

Thanks for the response guys. I have one more question: how could it be optimal to bfs/dfs from arbitrary vertices in each component(s)?

I thought of everything else but got stuck on this in contest. Maybe I misunderstood something?

Something like this:

Wouldn't you have to start your traversal at A, and not B or C?

After dijkstra from source vertex, you can start a dfs from the destination vertex. Number of shortest paths from source vertex to current vertex = SUM(number of shortest paths from source vertex to children of current vertex (given the child lies in the shortest path)). in dp₁ source vertex is s, in dp₂ source vertex is t

You can also do it in dijkstra like this when exploring a new vertex v from u:

if (d[v] > d[u] + dist)
    d[v] = d[u] + dist, dp[v] = dp[u], pq.emplace(...);
else if (d[v] == d[u] + dist)
    dp[v] += dp[u];

Where I can take official editorial ?

There are 4 shortest paths and there are no collisions, except the case when both use exactly the same path, so the answer is 4*3 = 12.

Do you have a url to some accepted submission, which prints 16?

great achievement, but how did you connect to internet, just curious?