trang chủ / đề bài / icpc22_mt_h

Thoát khỏi mê cung

Đề bài

Mô tả

Jeremy tham gia một sự kiện của công ty và chơi một trò chơi: thoát khỏi một mê cung. Anh có trong tay bản đồ của mê cung.

Mê cung có N phòng, đánh số từ 1 đến N. Jeremy xuất phát ở phòng 1, lối ra ở phòng N.

Có M lối đi hai chiều, mỗi lối đi nối hai phòng. Jeremy cần 1 đơn vị thời gian để đi qua một lối đi bất kỳ (vào và ra khỏi phòng không mất thời gian). Jeremy có thể đứng yên trong một phòng bao lâu tùy ý.

Hệ thống của trò chơi sẽ đặt thêm một số lối đi vào một số thời điểm (vào lúc bắt đầu phút đó). Jeremy có thể đi qua một lối đi ngay sau khi nó được đặt.

Ví dụ, ban đầu mê cung có các lối đi 1−2, 2−3, 3−4, 4−5, và lối đi nối phòng 2 với phòng 5 được đặt vào phút thứ 3. Một cách đi tối ưu:

  • Trong phút thứ nhất, Jeremy đi từ phòng 1 sang phòng 2.
  • Trong phút thứ hai, Jeremy đứng yên ở phòng 2.
  • Vào đầu phút thứ ba, hệ thống đặt lối đi từ phòng 2 sang phòng 5. Jeremy đi qua lối đi này ngay lập tức và tới phòng 5, lối ra.

Đáp án là 3 phút.

Hãy xác định số phút ít nhất Jeremy cần để hoàn thành trò chơi.

Dữ liệu vào

  • Dòng đầu tiên gồm hai số nguyên N, M (2≤N≤105, 0≤M≤2×105): số phòng và số lối đi ban đầu.
  • M dòng tiếp theo, dòng thứ i gồm hai số nguyên ui, vi (1≤ui,vi≤N): lối đi thứ i nối phòng ui và phòng vi.
  • Dòng thứ M+2 gồm một số nguyên K (0≤K≤2×105): số lối đi được đặt thêm.
  • K dòng tiếp theo, dòng thứ i gồm ba số nguyên ti, ui, vi (1≤ti≤109, 1≤ui,vi≤N): lối đi thứ i được đặt vào phút thứ ti và nối phòng ui với phòng vi.

Dữ liệu ra

In ra một số nguyên: số phút ít nhất. In ra −1 nếu Jeremy không thể hoàn thành trò chơi.

Ràng buộc

  • 2≤N≤105
  • 0≤M≤2×105
  • 0≤K≤2×105
  • 1≤ti≤109
  • 1≤ui,vi≤N

Ví dụ

Input Output Giải thích
5 4
1 2
3 4
2 3
5 4
1
3 2 5
3 Đây là ví dụ được mô tả ở trên.
4 3
3 1
1 2
2 3
1
10 1 4
10 Jeremy không cần đi đâu cả: anh đứng ở phòng 1 và đi sang phòng 4 ngay khi lối đi được đặt vào phút thứ 10.

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