Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

PTIT014H - 2014 Bài H - Dịch vụ truyền thông

Công ty cung cấp dịch vụ mạng ABC vừa thiết lập một mạng truyền thông bao gồm n nút và m kênh nối trực tiếp hai 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 thứ i cho phép truyền tin hai chiều từ nút ui tới nút vi có độ trễ là c(ui, vi) và với chi phí duy trì là 100×c(ui, vi). Có không quá một kênh truyền tin từ một nút đến một nút khác. Một đường truyền tin từ nút s đến nút t được biểu diễn dưới dạng một dãy liên tiếp các chỉ số của các nút, xuất phát từ s và kết thúc tại t, trong đó hai nút liên tiếp trong dãy có kênh nối trực tiếp giữa chúng. Độ trễ của đường truyền tin được định nghĩa là tổng độ trễ của các kênh nối trực tiếp trên đường truyền tin đó. Mạng của công ty là liên thông, nghĩa là luôn có đường truyền tin giữa hai máy bất kỳ.

Công ty lựa chọn ba nút x, y, z (1≤ x < y < z ≤ n) làm ba nút nguồn chứa nguồn dữ liệu, các nút còn lại gọi là nút xử lý. Khi đó, mỗi nút xử lý i sẽ chọn đường truyền có độ trễ nhỏ nhất trong số ba đường truyền với độ trễ nhỏ nhất từ ba nguồn x, y hoặc z đến nó làm đường truyền mà theo đó nó sẽ nhận dữ liệu. Ta gọi độ trễ của đường truyền mà theo đó nút xử lý i nhận dữ liệu là độ trễ của nút này và ký hiệu là di. Sau một thời gian hoạt động, công ty nhận thấy có thể loại bỏ một số kênh truyền mà các giá trị độ trễ của các nút xử lý là không thay đổi. Vì vậy, công ty muốn tìm cách loại bỏ một số kênh nối sao cho tổng chi phí duy trì các kênh còn lại là nhỏ nhất mà vẫn đảm bảo các giá trị độ trễ của các nút xử lý là không thay đổi.

Yêu cầu: Cho biết thông tin về m kênh truyền tin và k giả định chọn ba nút nguồn. Với mỗi giả định chọn ba nút nguồn, hãy tìm phương án loại bỏ một số kênh truyền tin trong số m kênh truyền tin sao cho tổng chi phí duy trì các kênh còn lại là nhỏ nhất mà vẫn đảm bảo các giá trị độ trễ của các nút xử lý là không thay đổi.

Input

Dữ liệu vào gồm nhiều bộ dữ liệu tương ứng với nhiều test. Dòng đầu tiên chứa một số nguyên dương không vượt quá 10 là số lượng các bộ dữ liệu. Các dòng tiếp theo chứa các bộ dữ liệu.

Mỗi bộ dữ liệu gồm một nhóm dòng có khuôn dạng:

  • Dòng thứ nhất chứa ba số nguyên dương n, m, k (n ≤ 500, m ≤ 10000, k ≤ 10000);
  • Dòng thứ i trong số m dòng tiếp theo chứa ba số nguyên dương ui, vi, ci cho biết thông tin về kênh truyền tin thứ i (i = 1, 2, ..., m). Giả thiết: uivi, ci ­109.

Dòng thứ j trong số k dòng tiếp theo chứa ba số nguyên j, yj, zj (1≤ xj < yj < zj ≤ n) mô tả giả định thứ j­­ (j = 1, 2, ..., k).

Output

Với mỗi bộ dữ liệu, ghi ra trên một số dòng, mỗi dòng ghi một số là tổng chi phí nhỏ nhất của phương án tìm được tương ứng với các giả định.

Example

Input:
1
6 6 2
1 2 1
1 3 1
2 3 1
1 4 5
2 5 5
3 6 5
1 2 3
1 5 6 Output: 1500
700

Được gửi lên bởi:adm
Ngày:2014-03-31
Thời gian chạy:4s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA

hide comments
2023-10-03 02:41:50
i'm dying too.
2023-10-03 02:41:15
mst
2023-10-03 02:40:22
mn ko yeu ban
2023-10-03 02:38:31
help i'm dying

Last edit: 2023-10-03 02:40:57
2023-10-03 02:37:57
minh chac chan bai nay co the giai bang luong
2023-10-03 02:37:11
help ko biet lam mn oi co phai mst + lca ko
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.