Xoá đỉnh và tổng khoảng cách
Đề bài
Mô tả
Cho một đồ thị có hướng, có trọng số gồm đỉnh, trong đó giữa mỗi cặp đỉnh phân biệt đều có cạnh theo cả hai chiều. Cạnh đi từ đỉnh tới đỉnh có độ dài .
Người ta lần lượt xoá đỉnh khỏi đồ thị: ở bước thứ , đỉnh bị xoá cùng với mọi cạnh đi vào và đi ra khỏi nó.
Trước mỗi bước xoá, hãy tính tổng độ dài đường đi ngắn nhất giữa mọi cặp có thứ tự gồm hai đỉnh phân biệt còn lại trong đồ thị. Đường đi ngắn nhất được phép đi qua bất kỳ đỉnh nào còn lại (và chỉ những đỉnh còn lại).
Dữ liệu vào
- Dòng đầu chứa số nguyên .
- dòng tiếp theo, dòng thứ chứa số nguyên là ma trận kề của đồ thị.
- Dòng cuối chứa số nguyên phân biệt là thứ tự các đỉnh bị xoá.
Dữ liệu ra
In ra số nguyên trên một dòng, số thứ là tổng cần tìm ngay trước bước xoá thứ .
Ràng buộc
- với ,
- , các đôi một phân biệt
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 2 0 5 4 0 1 2 |
9 0 | Trước bước 1, tổng là . Trước bước 2 chỉ còn đỉnh 2, tổng bằng 0. |
| 4 0 3 1 1 6 0 400 1 2 4 0 1 1 1 1 0 4 1 2 3 |
17 23 404 0 | Sau khi xoá đỉnh 4, còn các đỉnh 1, 2, 3 với tổng 23. Sau khi xoá thêm đỉnh 1, chỉ còn cạnh dài 400 và dài 4, tổng 404. |
| 1 0 1 |
0 | Chỉ có một đỉnh. |
Bình luận