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

COMNET - VOI 2013 - Mạng truyền thông

    Tổng công ty Z gồm N công ty con, đánh số từ 1-N. Mỗi công ty con có một máy chủ. Để đảm bảo truyền tin giữa các công ty, Z thuê M đường truyền tin để kết nối N máy chủ thành một mạng máy tính của Tổng công ty. Không có 2 đường truyền nối cùng 1 cặp máy chủ. Đường truyền i nối máy chủ của 2 công ty ui, vi có chi phí là wi. Mạng máy tính có tính thông suốt, nghĩa là từ một máy chủ có thể truyền tin đến một máy chủ bất kì khác bằng đường truyền trực tiếp hoặc qua nhiều đường trung gian.

    Một đường truyền gọi là không tiềm năng nếu như : một mặt, việc loại bỏ đường truyền này không làm mất tính thông suốt; mặt khác, nó phải có tính không tiềm năng, nghĩa là không thuộc bất cứ mạng con thông suốt gồm N máy chủ và N-1 đường truyền tin với tổng chi phí thuê bao nhỏ nhất nào của mạng máy tính.

    Trong thời gian tới, chi phí thuê bao của một số đường truyền tin thay đổi. Tổng công ty muốn xác định với chi phí mới thì đường truyền thứ k có là đường không tiềm năng hay không để xem xét chấm dựt việc thuê đường truyền này.

Input

  • Dòng đầu là T – số testcase. T nhóm dòng, mỗi nhóm cho thông tin về một testcase.
  • Dòng thứ nhất gồm 3 số nguyên dương N, M, Q (Q <= 30).
  • Dòng thứ i trong M dòng tiếp theo chứa 3 số nguyên dương ui, vi, wi (ui ≠ vi, wi < 109).
  • Dòng thứ j trong Q dòng tiếp theo mô tả giả định thứ j:
    • Số đầu tiên là chỉ số kj của đường truyền tin cần xem xét
    • Tiếp theo là sj ( sj <= 100) cho biết số lượng đường truyền có chi phí thuê mới
    • Cuối cùng là sj cặp số nguyên dương tp, cp cho biết đường truyền thứ tp có chi phí thuê mới là cp (cp < 109).

Output

  • Gồm T nhóm dòng, mỗi nhóm gồm Q dòng. Mỗi dòng là câu trả lời cho giả định tương ứng trong input. Ghi YES nếu câu trả lời là khẳng định và NO trong trường hợp ngược lại.

Example

Input:
1
3 3 2
1 2 1
1 3 2
2 3 3
3 2 2 4 3 4
1 1 1 4

Output:
NO
YES

Giới hạn

  • 30% số test đầu có 1 ≤ N ≤ 100;
  • 30% số test tiếp theo có 1 ≤ N ≤ 104 và 1 ≤ M ≤ 105;
  • 40% số test còn lại có 1 ≤ N ≤ 105 và 1 ≤ M ≤ 106.

Được gửi lên bởi:VOJ Team
Ngày:2013-01-12
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:VOI 2013 - Ngày 1

hide comments
2017-12-06 14:42:02
THAM KHẢO THUẬT TOÁN VÀ CODE TẠI:

http://yeulaptrinh.pw/1475/comnet-spoj/



2017-08-06 11:00:04
Xem code và cách giải ở https://vietcodes.github.io/code/30
2017-07-28 05:30:29
Code đã AC: http://shink.in/YBTuI
2017-06-11 19:17:55
Bài này 80 là wa hay tle vậy ạ? Code em đpt là O(mlogm + Q*m + Q*Smax*log(m))
2017-06-03 16:39:34
O(m+n) đếu AC
O(m) AC, dcm
2016-12-21 17:05:29
Thừa ĐK cầu => 43.33, bài này không xét cầu đâu...

Last edit: 2016-12-21 17:05:56
2016-12-21 15:12:45
http://ideone.com/Y81W96
Code Free


2016-11-03 15:21:39
Code pascal:
http://shink.in/YBTuI
2016-08-11 12:51:58
bài hay thật!
2016-06-29 03:57:15 NhiVD
Duy Anh đang code bài này :)
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.