Dịch vụ mạng

Điểm: 4,00 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 256M

Input: stdin

Output: stdout

Nguồn bài:

17-18 DHBB K11 B2

Dạng bài

Ngôn ngữ cho phép

C, C#, C++, Java, Javascript, Kotlin, Pascal, Python, Scratch

Hệ thống mạng truyền thông của công ty HP bao gồm $n$ nút và $m$ kênh nối trực tiếp một chiều giữa hai nút. Các nút được đánh số từ $1$ đến $n$ . Các kênh nối được đánh số từ $1$ đến $m$ . Kênh nối từ nút $i$ tới nút $j$ mất $t_{i j}$ đơn vị thời gian để truyền tin. Có thể có nhiều kênh truyền tin từ một nút đến một nút khác.

Để đánh giá hiệu suất hệ thống mạng, công ty đánh giá dựa trên giá trị $D I J$ . Giá trị $D I J$ được tính bằng tổng độ dài đường đi ngắn nhất giữa tất cả các cặp nút trong hệ thống mạng, cụ thể $D I J = \sum_{1 \leq i \neq j \leq n} d_{i j}$ , trong đó $d_{i j}$ là đường đi ngắn nhất từ nút $i$ đến nút $j$ .

Trong thời gian tới, công ty sẽ bổ sung thêm ba nút (ba nút này được đánh số tương ứng là $n + 1, n + 2, n + 3$ ) và một số kênh nối liên quan đến ba nút này vào hệ thống mạng. Công ty cần tính giá trị $D I J$ trên hệ thống mạng mới.

Yêu cầu: Cho biết hệ thống mạng truyền thông ban đầu của công ty HP và $k$ giả định bổ sung vào hệ thống mạng. Với mỗi giả định, hãy tính giá trị $D I J$ trên hệ thống mạng mới.

Dữ liệu vào

Dòng đầu tiên chứa $3$ số nguyên dương $n, m, k$ ( $n \leq 400$ ; $m \leq 10000$ ).
Dòng thứ $s$ ( $s = 1, 2, \dots, m$ ) trong số $m$ dòng tiếp theo ghi ba số nguyên dương $i_{s}, j_{s}, t_{i_{s} j_{s}}$ lần lượt là chỉ số đầu, chỉ số cuối và thời gian truyền tin của kênh thứ $s$ .
Dòng thứ $p$ ( $p = 1, 2, \dots, k$ ) trong số $k$ dòng tiếp theo mô tả giả định thứ $p$ có dạng: Số đầu tiên là số $e_{p}$ là số lượng kênh nối liên quan đến ba nút mới thêm vào hệ thống. Tiếp theo là $e_{p}$ bộ ba số $u_{h}, v_{h}, t_{u_{h} v_{h}}$ ( $h = 1, 2, \dots, e_{p}$ ) lần lượt là chỉ số đầu, chỉ số cuối và thời gian truyền tin của $e_{p}$ kênh nối bổ sung.

Dữ liệu đảm bảo có đường truyền từ một nút đến một nút bất kì khác.

Dữ liệu ra

Ghi $k$ dòng, mỗi dòng chứa một số là giá trị $D I J$ tương ứng với từng giả định.

Ràng buộc

Có $40 %$ số test ứng với $40 %$ số điểm của bài có $k = 1$ .
Có $20 %$ số test khác ứng với $20 %$ số điểm của bài có $k \leq 3$ .
Có $40 %$ số test còn lại ứng với $40 %$ số điểm của bài có $k \leq 400$ .

Ví dụ

Input	Output	Giải thích
3 3 1 1 2 5 2 3 5 3 1 5 4 1 4 1 4 5 1 5 6 1 6 1 1	183	Đồ thị ban đầu có $3$ nút với các cạnh $1 \to 2$ (trọng số $5$ ), $2 \to 3$ (trọng số $5$ ), $3 \to 1$ (trọng số $5$ ). Giả định bổ sung $3$ nút mới ( $4, 5, 6$ ) với $4$ kênh: $1 \to 4$ (trọng số $1$ ), $4 \to 5$ (trọng số $1$ ), $5 \to 6$ (trọng số $1$ ), $6 \to 1$ (trọng số $1$ ). Đồ thị mới có $6$ nút, tổng đường đi ngắn nhất giữa tất cả các cặp là $183$ .

Bình luận

LeVoDanh

đã bình luận lúc 26, Tháng 11, 2025, 11:35

chào nhé!