[AI Readability Summary] This problem asks Azer and Baijan to compute shortest paths from node 0 when each side knows only part of the graph. The core idea is to convert naive Dijkstra into a communication protocol: in each round, the two parties exchange the local best distance increment and the winning node ID. Keywords: Distributed Shortest Path, Communication Complexity, Dijkstra.
Technical specifications define the solution space
| Parameter | Value |
|---|---|
| Problem | JOISC 2019 Two Transportations |
| Primary Language | C++ |
| Graph Model | Undirected connected graph |
| Node Limit | N ≤ 2000 (inferred from the code and communication design) |
| Edge Weight Range | Positive integers, and ≤ 500 |
| Communication Limit | 58,000 bits |
| Target Algorithm | O(n^2) naive Dijkstra |
| Protocol Key Point | 9-bit distance increment + 11-bit node ID |
| Core Dependencies | vector, pair, bit transfer interfaces SendA / SendB |
| Star Count | Not provided in the original data |
AI Visual Insight: The problem is not about accelerating shortest path computation. It is about compressing each Dijkstra decision into a fixed-size message that both parties can replay consistently.
This problem is best understood as shortest path protocol design under limited communication
The essence of the task is not ordinary shortest path computation, but shortest path computation with split information. Azer knows one subset of edges, and Baijan knows another. Neither side can reconstruct the full graph alone, so the key challenge is not graph construction, but synchronizing every Dijkstra decision.
Because the graph is relatively dense and the number of nodes is small, heap optimization is not the important part. What matters is this: if both parties can identify the current globally minimal unsettled node in each round, then each side can relax the edges it knows locally, and both will eventually obtain the same final answer.
The formal state is synchronized by replaying Dijkstra round by round
In naive Dijkstra, each round requires two operations:
- Find the unsettled node with the smallest distance.
- Mark that node as settled and relax all of its adjacent edges.
In this problem, both sides can compute the locally optimal unsettled node from their own perspective. They then communicate to compare the two distances. The smaller one becomes the new settled node for the round. If that node comes from the other side, the winner sends the node ID so both sides stay synchronized.
void FindA() {
u = -1;
for (int i = 0; i < N; ++i) {
// Find the locally minimal distance among unsettled nodes
if (!f[i] && (u == -1 || d[i] < d[u])) u = i;
}
if (u == -1) return;
t = d[u];
}This logic maintains Azer’s current candidate settled node and its shortest known distance.
The communication budget works because the protocol sends increments instead of absolute distances
If the protocol sent absolute shortest path values directly, the bit count could become too large. However, Dijkstra provides a critical property: the distance of a newly settled node cannot exceed the previous settled distance by very much. Since the maximum edge weight is only 500, the shortest path difference between two consecutive settled nodes is at most 500.
Therefore, each round only needs to send d[u] - lst. This value lies in [0, 500], so 9 bits are enough. The code also reserves 511 as an INF sentinel to represent an unreachable local candidate.
The distance comparison protocol is the key compression point in the entire design
In each round, both parties first send 9 bits:
- They encode the distance increment of the current candidate relative to the previous settled node.
- If the local candidate is
INF, they send511.
After receiving the other side’s 9 bits, both parties can reconstruct the other candidate distance and compare the two. If the local candidate wins, that side sends the node ID. If the remote candidate wins, the local side waits to receive the ID.
for (int i = 0; i < 9; ++i) {
// Send the distance increment; use 511 as the INF sentinel
SendA((d[u] == INF ? 511 : d[u] - lst) >> i & 1);
}This code performs the most important compressed transmission in each round.
The node ID uses 11 bits, which exactly covers a graph of about 2000 nodes
Because N is on the order of 2000, a node ID needs at most 11 bits. Once the round winner is determined, only the winning side needs to send its node ID, and the other side can then perform the same settle-and-relax step.
The total communication cost per round is approximately:
- Distance comparison from both sides:
9 + 9 = 18 bits - Winner sends node ID:
11 bits
That gives:
29 × 2000 = 58000 bitsThis exactly matches the problem limit, which shows that the protocol is not merely accepted by chance. It is a budget-tight design.
Local relaxation remains standard Dijkstra with no extra trick
Once the new global settled node is known, both parties can perform ordinary relaxation on the edges they hold locally. Since the graph’s full edge set is split between the two participants, local relaxation on both sides, combined with synchronization after every round, causes d[] to gradually converge to the true shortest path values in the complete graph.
void UpdA() {
lst = d[u] = t;
f[u] = true; // Mark this node as settled
for (auto [v, w] : g[u]) {
// Relax the locally known edges using the new settled node
d[v] = min(d[v], d[u] + w);
}
}This code shows that once the settled node is fixed, the local distance array is updated exactly as in standard Dijkstra.
Azer and Baijan use mirrored implementations, and the only real difference is tie-breaking
The two implementations are almost perfectly symmetric: FindA/FindB, UpdA/UpdB, and ReceiveA/ReceiveB handle search, update, and packet reception respectively.
One subtle detail matters: Azer uses if(t<=x), while Baijan uses if(t<x). That means Azer wins ties. This rule must be globally consistent. Otherwise, the two sides may disagree on which node becomes settled in a given round, and the protocol fails immediately.
The receive logic is essentially a two-phase state machine
In phase one, the side receives the 9-bit distance value. In phase two, if the other side wins, it then receives the 11-bit node ID. The code uses mk to mark whether it has entered phase two, and buf to collect the bit stream.
if (!mk && buf.size() == 9) {
// First parse the other side's candidate distance
}
if (mk && buf.size() == 11) {
// Then parse the winning node ID sent by the other side
}This structure shows that the communication process is a stable fixed-length protocol, not a free-form message format.
The key lesson is to translate an algorithmic process into a communication protocol
If you view this problem only as a shortest path problem, it is not especially difficult. The real challenge is to abstract Dijkstra’s node-selection step into the minimum possible information exchange. The edge weight bound of 500 creates room for distance compression, and the node bound of about 2000 determines the ID width. Together, these constraints make the protocol feasible.
From a competitive programming perspective, this is a classic hybrid problem that combines algorithm design with encoding design. You need to know shortest path algorithms, but you also need to prove what to send in each round, how many bits it costs, and why the total never exceeds the budget.
FAQ
Q1: Why can we use naive Dijkstra instead of heap-optimized Dijkstra?
Because the number of nodes is small, and the true bottleneck is communication complexity rather than time complexity. Naive Dijkstra makes it much easier to protocolize the “pick the minimum node each round” process.
Q2: Why is the distance increment guaranteed to be at most 500?
In Dijkstra, a newly settled node is typically reached by extending from a previously settled node through one edge. Since the maximum edge weight is 500, the shortest path difference between consecutive settled nodes cannot exceed 500, so 9 bits are enough.
Q3: Why must ties always be broken in favor of one fixed side?
If both sides insist on their own local choice when distances are equal, the settled-node sets diverge. Once that happens, all later synchronization of d[] becomes invalid. A fixed tie-breaking rule is necessary for protocol consistency.
Core Summary: This article reconstructs the JOISC 2019 Two Transportations solution and focuses on collaborative shortest path computation over a graph whose information is split across two endpoints. The core idea is to rewrite naive Dijkstra as a low-communication protocol: in each round, the participants exchange only the minimum distance increment and the node ID, allowing them to recover shortest paths from source node 0 within 58,000 bits.