Các lượt nộp
    Danh sách bài
    Trang chủ
    Báo lỗi

    solution

    Đề bài: [Giải thuật] Đường đi ngắn nhất Dijkstra

    Cho đồ thị có hướng có trọng số không âm gồm nnn đỉnh và mmm cung. Tìm độ dài đường đi ngắn nhất từ đỉnh 111 đến đỉnh nnn. Nếu không tới được, in −1-1−1.

    • Định dạng đầu vào:

      Dòng đầu chứa nnn và mmm. mmm dòng sau, mỗi dòng ba số uuu vvv www: cung từ uuu tới vvv trọng số www.

    • Ràng buộc đầu vào:

      1≤n≤1051 \le n \le 10^51≤n≤105, 0≤m≤2×1050 \le m \le 2\times10^50≤m≤2×105, 0≤w≤1090 \le w \le 10^90≤w≤109.

    • Định dạng đầu ra:

      In độ dài đường đi ngắn nhất từ 111 đến nnn, hoặc −1-1−1 nếu không tồn tại.

    Ví dụ:

    Đầu vào:

    4 4
1 2 1
2 3 2
1 3 5
3 4 1

    Đầu ra:

    4

    Giải thích:

    Đường 1->2->3->4 có tổng 1+2+1=4, ngắn hơn 1->3->4 (5+1=6).

    Đang tải editor...