trang chủ / đề bài / gr11_bottle

Con đường ít dốc nhất

Đề bài

Mô tả

Một vùng núi có n địa điểm đánh số từ 1 đến n và m con đường hai chiều; con đường thứ i nối địa điểm ui với vi và có độ dốc wi. Một chiếc xe đi được trên một tuyến đường khi và chỉ khi độ dốc của mọi con đường trên tuyến đều không vượt quá khả năng leo dốc của xe.

Có q câu hỏi, mỗi câu hỏi gồm hai địa điểm a và b: hãy tìm khả năng leo dốc nhỏ nhất mà xe cần có để đi từ a tới b. Nói cách khác, trong tất cả các tuyến đường từ a tới b, hãy tìm tuyến có con đường dốc nhất là thoải nhất, và in ra độ dốc của con đường dốc nhất đó.

Quy ước: nếu a=b thì đáp án là 0; nếu không có tuyến đường nào từ a tới b thì đáp án là −1. Có thể có nhiều con đường nối cùng một cặp địa điểm và có con đường với ui=vi.

Dữ liệu vào

  • Dòng đầu tiên chứa ba số nguyên n, m, q.
  • m dòng tiếp theo, dòng thứ i chứa ba số nguyên ui,vi,wi.
  • q dòng tiếp theo, mỗi dòng chứa hai số nguyên a,b.

Dữ liệu ra

In ra q dòng, dòng thứ j là đáp án của câu hỏi thứ j.

Ràng buộc

  • 1≤n≤5·104
  • 0≤m≤105
  • 1≤q≤105
  • 1≤ui,vi,a,b≤n
  • 1≤wi≤109

Ví dụ

Input Output Giải thích
5 6 4
1 2 4
2 3 2
1 3 7
3 4 5
4 5 1
2 5 9
1 3
1 5
4 5
3 3		 4
5
1
0		 Từ 1 tới 3: đi 1→2→3 thì con đường dốc nhất có độ dốc 4, tốt hơn đi thẳng (độ dốc 7). Từ 1 tới 5: đi 1→2→3→4→5, dốc nhất là 5.
4 2 3
1 2 3
3 4 6
1 2
2 3
4 3		 3
-1
6		 Không có tuyến đường nào nối {1,2} với {3,4}.

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