trang chủ / đề bài / icpc20_reg_i

Trao đổi tình báo

Đề bài

Mô tả

Dù vẫn còn là học sinh trung học, Carmen và Juni đã là những điệp viên hàng đầu.

Carmen và Juni sống ở Byteland, có thể mô hình hóa bằng một đồ thị vô hướng liên thông gồm n đỉnh và m cạnh. Sáng nay, đúng 8 giờ, Carmen đi từ nhà ở đỉnh hc đến trường ở đỉnh sc. Cũng đúng 8 giờ, Juni đi từ nhà ở đỉnh hj đến trường ở đỉnh sj.

Trên đường đến trường hôm nay, Carmen và Juni muốn trao đổi thông tin tình báo đã thu thập được. Là những điệp viên hàng đầu, họ chỉ cần ở cùng một vị trí (tại một đỉnh hoặc tại một điểm trên một cạnh) vào cùng một thời điểm là có thể trao đổi thông tin.

Để đơn giản, giả sử Carmen và Juni ở lại trường mãi mãi sau khi đến trường. Điều này cũng có nghĩa là sau khi đến trường, họ có thể chờ ở đó và trao đổi thông tin vào một thời điểm muộn hơn.

Tuy nhiên, Carmen và Juni không có thời gian để lãng phí: mỗi người luôn đi theo một đường đi ngắn nhất từ nhà đến trường. Nếu có nhiều đường đi ngắn nhất, mỗi người có thể chọn bất kỳ đường nào trong số đó.

Carmen và Juni muốn biết có bao nhiêu vị trí khác nhau mà họ có thể trao đổi thông tin. Lưu ý rằng nếu họ có thể gặp nhau tại cùng một vị trí vào hai thời điểm khác nhau, vị trí đó chỉ được tính một lần. Nếu họ có thể gặp nhau tại hai vị trí khác nhau trên cùng một cạnh, cả hai vị trí đều được tính.

Carmen và Juni có cùng tốc độ và tốc độ của họ không thay đổi. Nếu đi hết một cạnh mất t phút thì đi được phần x của cạnh đó (với 0≤x≤1) mất đúng x·t phút.

Dữ liệu vào

Dữ liệu vào gồm nhiều bộ dữ liệu. Mỗi bộ dữ liệu có dạng:

  • Dòng đầu tiên chứa hai số nguyên n và m.
  • Dòng thứ hai chứa bốn số nguyên hc, sc, hj, sj.
  • m dòng tiếp theo, dòng thứ i chứa ba số nguyên u, v, t: có một cạnh nối u và v, và cả Carmen lẫn Juni đều mất t phút để đi hết cạnh này. Đồ thị được đảm bảo liên thông.

Dữ liệu vào kết thúc bằng một dòng chứa hai số 0; không cần xử lý dòng này.

Dữ liệu ra

Với mỗi bộ dữ liệu, gọi r là số vị trí khác nhau mà Carmen và Juni có thể trao đổi thông tin. Nếu r>109, in ra −1 trên một dòng. Ngược lại, in ra r trên một dòng.

Ràng buộc

  • 1≤n,m≤5·105.
  • 1≤hc,sc,hj,sj≤n; hc≠sc; hj≠sj.
  • 1≤u,v≤n; u≠v; 1≤t≤109.
  • Tổng n của tất cả các bộ dữ liệu không vượt quá 5·105. Tổng m của tất cả các bộ dữ liệu không vượt quá 5·105.

Ví dụ

Input Output Giải thích
5 6
1 3 4 5
1 2 10
2 3 20
1 3 30
4 2 10
2 5 30
4 5 40
0 0
1 Carmen đi từ 1 đến 3 có hai đường ngắn nhất độ dài 30; Juni đi từ 4 đến 5 có hai đường ngắn nhất độ dài 40. Họ có thể gặp nhau tại đỉnh 2 lúc 8 giờ 10 nếu Carmen đi 1→2→3 và Juni đi 4→2→5.
5 6
1 3 4 5
1 2 10
2 3 20
1 3 20
4 2 10
2 5 30
4 5 40
0 0
0 Carmen chỉ có một đường ngắn nhất độ dài 20 là 1→3, nên họ không thể gặp nhau.
3 2
1 3 2 3
1 3 10
2 3 20
0 0
1 Cả hai cùng học ở đỉnh 3. Carmen đến trường lúc 8 giờ 10, Juni đến lúc 8 giờ 20. Carmen có thể chờ ở trường đến khi Juni tới và trao đổi thông tin lúc 8 giờ 20.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0