Floyd hoặc Dijkstra (Cơ bản)

View as PDF
Submit solution
Points: 0.06 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Cho đơn đồ thị vô hướng ~N~ đỉnh và ~M~ cạnh, trọng số các cạnh đều nguyên dương. Có ~2~ loại câu hỏi:

~0~ ~u~ ~v~: Cho biết đường đi ngắn nhất từ ~u~ tới ~v~ có độ dài là bao nhiêu.

~1~ ~u~ ~v~: Hãy chỉ ra ~1~ đường đi ngắn nhất từ ~u \rightarrow v~

Bài cơ bản này nhằm kiểm tra kỹ năng xây dựng các module chương trình con dành cho truy vết ~1~ cách hợp lý, sử dụng nhuần nhuyễn chương trình con, lời gọi hàm.

Input

Dòng ~1~: ~3~ số nguyên ~N~, ~M~, ~K~. ~\left(1 \leq N \leq 100, 1 \leq M \leq \frac{N(N-1)}{2}, 1 \leq K \leq 1000\right)~

~M~ dòng tiếp theo, dòng thứ ~i~ gồm ~3~ số nguyên dương ~u~, ~v~, ~c~ cho biết cạnh (~u~, ~v~) có trọng số là ~c~ ~(1 \leq c \leq 10000)~

~K~ dòng tiếp theo là ~K~ câu hỏi, dòng thứ ~j~ sẽ có định dạng như đã nêu ở trên.

Output

Ứng với mỗi câu hỏi trong ~K~ câu hỏi thì ta phải trả lời trên mỗi dòng như sau.

Câu hỏi ~0~ ~u~ ~v~: Ghi ra ~1~ số nguyên duy nhất là độ dài đường đi ngắn nhất từ ~u \rightarrow v~.

Câu hỏi ~1~ ~u~ ~v~: Ghi ra số đầu tiên là số ~X~ là số đỉnh trên đường đi ngắn nhất này, tiếp đó ghi ra ~X~ số là chỉ số các đỉnh theo thứ tự xuất hiện trên hành trình.

Sample Input

3 3 2
1 2 3
2 3 1
1 3 5
0 1 2
1 1 3

Sample Output

3
3 1 2 3

Note

Download test và solution tại đây.

Lưu ý: Do thay đổi về trình chấm (trình chấm mới không chấp nhận 1 đỉnh tự quay lại chính nó nếu không có cạnh ở input), do đó solution ở trên sẽ không AC ở VNOJ.

Comments

Please read the guidelines before commenting.


  • 0
    minzdapoet1102  commented on Aug. 30, 2024, 4:59 a.m.

    Mình có 2 thắc mắc xin nhờ mọi người giải đáp

    1. Trường hợp không tồn tại đường đi từ $u$ đến $v$ thì in ra gì?
    2. Trường hợp truy vấn loại 2 cho đường đi từ $u$ đến chính nó, và đường đi ngắn nhất là đường đi $u -> u -> u$, thì kết quả trả về là $1 u$ hay $3 u u u$? Xin cảm ơn mọi người!

  • -5
    SpiritedAway  commented on May 1, 2023, 1:21 p.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


    • -1
      trongtenlinhcbhk64  commented on May 6, 2023, 5:50 p.m.

      Trường hợp đó đường đi có một đỉnh là chính đỉnh đó nha bạn


  • -5
    LêThanhThảo  commented on Aug. 11, 2022, 3:19 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


    • 11
      hungntils  commented on April 19, 2023, 9:16 a.m.

      Lưu ý cái này ở trên nhé bạn: Do thay đổi về trình chấm (trình chấm mới không chấp nhận 1 đỉnh tự quay lại chính nó nếu không có cạnh ở input), do đó solution ở trên sẽ không AC ở VNOJ.


      • -2
        SpiritedAway  commented on May 1, 2023, 9:59 a.m.

        z output là gì khi vào trường hợp đó: -1 hay không in gì


    • -2
      minhducle31o  commented on April 19, 2023, 9:10 a.m.

      mình cũng bị vậy


      • -2
        Marx_Lenin  commented on April 5, 2024, 1:42 a.m.

        real?