Shortest Paths Revisited via Floyd-Warshall

The problem Luogu P1119 (Post‑Disaster Reconstruction) provides a natural opportunity to exploit the transitive nature of the Floyd‑Warshall algorithm. We are given a graph where certain vertices become usable over time and must answer online queries about shortest paths. Instead of repeated Dijkstra, we can interleave vertex activations with the triple‑loop update.

The core of Floyd‑Warshall computes all‑pairs shortest paths by gradually allowing paths to pass through a growing set of intermediate vertices. In this problem, vertices are restored chronologically; therefore we can activate a vertex by letting it serve as the pivot for the relaxation step. Only when both endpoints of a query have been restored do we answer it.

// Allow vertex 'mid' to act as an intermediate point
void incorporate_vertex(int mid) {
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            if (shortest[i][j] > shortest[i][mid] + shortest[mid][j])
                shortest[i][j] = shortest[i][mid] + shortest[mid][j];
}

The complete solution reads the restoration times, initialises the distance matrix, then processes queries in chronological order. A pointer cur iterates over vertices whose repair time does not exceed the query time; each is incorporated by calling incorporate_vertex(cur). If any queried vertex is still unavailable or the distance remains at infinity, output ‑1.

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 210, INF = 1e9 + 10;
int dist[MAXN][MAXN], repair_time[MAXN];
int n, m;

void activate_vertex(int k) {
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; ++i) scanf("%d", &repair_time[i]);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) dist[i][j] = INF;
        dist[i][i] = 0;
    }
    for (int i = 0; i < m; ++i) {
        int u, v, w; scanf("%d%d%d", &u, &v, &w);
        dist[u][v] = dist[v][u] = w;
    }

    int q; scanf("%d", &q);
    int nxt = 0;
    while (q--) {
        int u, v, t; scanf("%d%d%d", &u, &v, &t);
        while (nxt < n && repair_time[nxt] <= t) {
            activate_vertex(nxt);
            ++nxt;
        }
        if (repair_time[u] > t || repair_time[v] > t || dist[u][v] == INF)
            puts("-1");
        else
            printf("%d\n", dist[u][v]);
    }
    return 0;
}

Finding the Minimum Cycle in an Undirected Graph

The same intermediate‑vertex concept solves Luogu P6175. A cycle can be formed by combining a known shortest path between two vertices with two edges that share a common pivot vertex. While running Floyd‑Warshall, before we update the shortest path using the pivot k, we try to close a cycle that goes from i to j via some shortest path not yet using k, and then returns via the edges (i,k) and (k,j).

int min_cycle = INF;
for (int k = 1; k <= n; ++k) {
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            if (i != j && adj[i][k] && adj[k][j])
                min_cycle = min(min_cycle, d[i][j] + adj[i][k] + adj[k][j]);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}

Extracting the Longest Common Part of Two Shortest Paths

Luogu P2149 asks for the longest path shared by the shortest routes between two source‑sink pairs. The method builds on the idea of replacement paths. For a given pair, an edge (u,v) lies on some shortest path if the sum of distances from the source to u, from v to the sink, and the edge weight equals the global shortest distance. By running Dijkstra four times (forward and reverse for each pair), we can mark edges that belong to the respective shortest‑path DAGs. The overlap may be traversed in the same direction or in opposite directions; therefore we perform a topological DP twice and keep the maximum length.

Multi‑Source Shortest Paths for the Traveller

Luogu P5304 (Traveller) can be solved by binary splitting: for each bit position, partition the special vertices into two sets based on the bit, connect a super‑source to one set and a super‑sink to the other, and run Dijkstra. Another elegant approach treats every special vertex both as a candidate source and as a candidate destination. We run a forward Dijkstra from all special vertices simultaneously and a reverse Dijkstra to all special vertices. Then we iterate over all edges (u,v,w). If the forward distance to u and the reverse distance from v together with w give a valid path, we update the answer, taking care to exclude trivial loops (when both ends belong to the same special vertex).

Strongly Connected Components and Reachability Tree

Luogu P7737 (NOI2021 Celebration) first requires condensing the directed graph into a DAG using Tarjan’s algorithm. The problem guarantees a special property: for any three cities, if both x and y can reach z, then either x can reach y or y can reach x. This implies that each vertex in the DAG has indegree at most one, otherwise two different ancestors would lead to a vertex without comparable reachability. Hence, after removing redundant edges, the DAG becomes a directed tree (all edges point away from the root).

Let subtree(x) denote the set of vertices in the subtree of x, and ancestors(x) the vertices on the path from the root to x. For a query (s, t), the basic answer is the union of subtree(s) and ancestors(t). When adding an extra temporary edge (u, v), we extend the reachable sets: if u is in the forward reachable set from s, that set absorbs subtree(v); if v lies in the backward reachable set of t, that set absorbs ancestors(u). The final result is the size of the union, which can be computed using a heavy‑light decomposition and sorting the DFS intervals.

Eulerian Trail Conditions

Several classical results guide the existence of Eulerian trails:

• An undirected connected graph has an Eulerian trail iff the number of vertices of odd degree is either 0 or 2. When the count is 0, the graph contains an Eulerian circuit.
• If an undirected connected graph has 2k odd vertices, it can be decomposed into k edge‑disjoint trails, and atleast k trails are necessary.
• For a directed graph to be Eulerian (circuit), it must be weakly connected and every vertex must have equal indegree and outdegree. A directed graph is semi‑Eulerian (trail) if it is weakly connected, exactly two vertices have indegree equal to outdegree minus one and plus one respectively, and all other vertices have balanced degree.

A direct application appears in Luogu P1341 (Unordered Letter Pairs), where we need to find an Eulerian path on a graph whose vertices are letters.

Differential Constraints – The Cashier Problem

This classic scheduling problem uses a system of difference constraints. We define:

• num[i] – number of people willing to start work at hour i (0‑23).
• x[i] – actual number of employees starting at hour i, bounded by 0 ≤ x[i] ≤ num[i].
• r[i] – minimum required number of workers for the hour i.
• s[i] = x[1] + x[2] + … + x[i] (prefix sum, with s[0]=0).

The demand constraints translate to:

s[i] - s[i-8] ≥ r[i]           for 8 ≤ i ≤ 23
s[23] + s[i] - s[i+16] ≥ r[i]  for 0 ≤ i ≤ 7
0 ≤ s[i] - s[i-1] ≤ num[i]     for 0 ≤ i ≤ 23 (s[-1] treated as 0)

By moving s[23] to the right side and treating it as a parameter, we obtain a standard system: each inequality is of the form A - B ≥ C. For a fixed guess of s[23] = T, we construct a graph where an edge B → A with weight C represents A - B ≥ C. We then run a longest‑path / Bellman‑Ford algorithm to check feasibility. Binary search or linear scan over possible values of T yields the minimum feasible total workforce.