Official Analysis (C++)

Let's construct a graph, and for each tuple $(a, b, x)$ we add a directed edge from $a$ to $b$ with weight $x$. Observe that there cannot be any cycles in this graph, since otherwise no solution would exist. Therefore, we can process the sessions (tuples) in order using topological sort.

Without loss of generality, suppose that the topological sort ordering is $1, 2, \dots , N$ so that all edges satisfy $a \lt b$. Then, for each directed edge in increasing order of $a$, we set $S_b = \max(S_b, S_a + x)$, since the earliest possible date is the later one of $S_b$ and $S_a + x$.

Once we process all edges, the resulting $S_1, S_2, \dots , S_N$ are the earliest possible dates with the given edge constraints, and we are done.

Implementation

Time Complexity: $\mathcal{O}(N+M)$

Copy
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

void topo_sorting(vector<vector<pair<int, int>>> &graph, vector<bool> &visited,
                  vector<int> &toposort, int node) {
	visited[node] = true;
	for (auto i : graph[node]) {
		int a, b;
		tie(a, b) = i;

Copy
import java.io.*;
import java.util.*;

public class timeline {
	public static void main(String[] args) throws IOException {
		BufferedReader r = new BufferedReader(new FileReader("timeline.in"));
		PrintWriter pw = new PrintWriter("timeline.out");
		StringTokenizer st = new StringTokenizer(r.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());