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.|

DHSERV - Dịch vụ truyền thông

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/dhserv


Công ty cung cấp dịch vụ mạng HDS vừa thiết lập một mạng truyền thông, mạng 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 thứ i cho phép truyền tin (một chiều) từ nút ui tới nút vi và có độ trễ là 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. Độ 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 đó. Để đánh giá mạng truyền thông, công ty đưa ra kịch bản kiểm tra như sau: Ban đầu tất cả n nút đều ở chế độ không chuyển tiếp tin; có k thao tác thuộc một trong hai loại sau:

- Loại 1, nhận một chỉ số x (1 ≤ x ≤ n) có ý nghĩa: kích hoạt nút x sang chế độ được chuyển tiếp tin;
- Loại 2, nhận hai chỉ số x, y (1 ≤ x, y ≤ n) có ý nghĩa: cần tính độ trễ của đường truyền tin từ nút x đến nút y (không đi qua nút ở chế độ không chuyển tiếp tin) có độ trễ nhỏ nhất, nếu không tồn tại đường truyền thì đưa ra -1.
Yêu cầu: Cho biết mạng truyền thông của công ty HDS và kịch bản kiểm tra gồm k thao tác, hãy thực hiện lần lượt từng thao tác và với mỗi thao tác loại 2 thì đưa ra độ trễ nhỏ nhất cần tính.:
  • Loại 1, nhận một chỉ số x (1 ≤ x ≤ n) có ý nghĩa: kích hoạt nút x sang chế độ được chuyển tiếp tin;
  • Loại 2, nhận hai chỉ số x, y (1 ≤ x, y ≤ n) có ý nghĩa: cần tính độ trễ của đường truyền tin từ nút x đến nút y (không đi qua nút ở chế độ không chuyển tiếp tin) có độ trễ nhỏ nhất, nếu không tồn tại đường truyền thì đưa ra -1.

Yêu cầu: Cho biết mạng truyền thông của công ty HDS và kịch bản kiểm tra gồm k thao tác, hãy thực hiện lần lượt từng thao tác và với mỗi thao tác loại 2 thì đưa ra độ trễ nhỏ nhất cần tính.

Dữ liệu: Vào từ thiết bị vào chuẩn:

 

  • Dòng đầu tiên chứa 3 số nguyên dương n, m, k;
  • Dòng thứ i trong số m dòng tiếp theo ghi ba số nguyên dương ui, vi, c(ui, vi) lần lượt là chỉ số đầu, chỉ số cuối và độ trễ của kênh thứ i. Độ trễ của các kênh là nhỏ hơn 10^9.
  • k dòng tiếp theo mô tả kịch bản, cụ thể:
    • Nếu thao tác thứ j thuộc loại 1 thì dòng thứ j gồm 2 số, số thứ nhất bằng 1 và số thứ hai là chỉ số nút;
    • Nếu thao tác thứ j thuộc loại 2 thì dòng thứ j gồm 3 số, số thứ nhất bằng 2 và hai số sau là hai chỉ số nút.

 

Các số trên cùng một dòng được ghi cách nhau ít nhất một dấu cách.

Kết quả: Ghi ra thiết bị ra chuẩn một số dòng, mỗi dòng là câu trả lời cho thao tác loại 2 xuất hiện lần lượt trong kịch bản.

 

  • Subtask 1 (20/70 điểm): Giả thiết có n ≤ 10, k ≤ 10.
  • Subtask 2 (20/70 điểm): Giả thiết có n ≤ 100, k ≤ 10^2.
  • Subtask 3 (30/70 điểm): Giả thiết có n ≤ 500, k ≤ 10^6.

Ví dụ:

Dữ liệu

4 5 5

1 4 1

1 3 5

1 2 1

4 3 1

2 3 2

2 1 3

1 2

2 1 3

1 4

2 1 3

Kết quả

5

3

2

 


Được gửi lên bởi:Lê Đôn Khuê
Ngày:2014-04-20
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ASM64 GOSU PERL6 PYPY RUST SED
Nguồn bài:HSG Duyên hải và Đồng bằng Bắc Bộ 2014

hide comments
2021-05-27 18:00:28
Tham khảo: https://vnspoj.github.io/problems/DHSERV
2020-02-28 09:16:28
test yếu ạ :))
2019-06-12 06:19:30
một đấm ac :)
2018-10-31 07:23:13
Dijkstra chục đấm vẫn 92.86 :)) floyd cho nhanh
CYB
2018-10-28 12:38:57
=)))) 1 Hit AC
AC với Cin cout + Ios
frostpixel aka.How 2 AC
2017-09-11 17:53:41
test yeu
2016-12-03 15:00:34
thế quái nào mình chỉ chép lại từ pas sang c++ mà ko ac @@ toàn 0đ 0mem @@
2016-12-03 09:43:17
cin cout TLE 92.86.
scanf printf AC 100
2016-08-28 08:34:54
Mỗi truy vấn 1 hết N^2 nhưng chỉ có tối đa N truy vấn loại 1 => O(k + n ^ 3)
2016-07-22 12:26:36 xin đừng quên tôi
Tham khảo thuật toán và code tại: yeulaptrinh.pw/304/dhserv-spoj/
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.