<p><strong>Ý tưởng</strong></p><ul><li>Tý đi từ Ha → Sa theo đường ngắn nhất</li><li>Tèo đi từ Hb → Sb theo đường ngắn nhất</li></ul><p>=>Ta cần tìm <strong>đỉnh i</strong> sao cho:</p><ul><li>Tý đi từ Ha → i nằm trên đường ngắn nhất tới Sa</li><li>Tèo đi từ Hb → i nằm trên đường ngắn nhất tới Sb</li><li>Và <strong>thời gian đến i của 2 người là bằng nhau</strong></li></ul><p><strong>Cách làm</strong></p><p>Dùng Dijkstra 4 lần:</p><ul><li>dHa[i]: từ Ha → i</li><li>dSa[i]: từ Sa → i</li><li>dHb[i]: từ Hb → i</li><li>dSb[i]: từ Sb → i</li></ul><p><strong>Một đỉnh i hợp lệ nếu:</strong></p><p>dHa[i] + dSa[i] == dHa[Sa]<br>dHb[i] + dSb[i] == dHb[Sb]</p><p>Và: dHa[i] == dHb[i]</p><p>=> Lấy <strong>min dHa[i]</strong></p>