Nâng cấp đường (OLP 10 - 2019)

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Thời gian:
Python 3 10.0s
Tác giả:
Small
Dạng bài
Điểm: 1700 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Hành tinh Marvelous Land gồm \(N\) thành phố, được kết nối với nhau bởi \(M\) tuyến đường hai chiều. Giữa hai thành phố chỉ có tối đa một tuyến đường nối chúng và không có tuyến đường nào nối một thành phố tới chính nó. Các thành phố được đánh số từ 1 tới \(N\). Trong đó có 2 thành phố là trung tâm kinh tế quan trọng là thành phố 1 và thành phố \(N\). Tuyến đường thứ \(i\) cho phép đi lại giữa hai thành phố \(u_i\) và \(v_i\) với \(t_i\) đơn vị thời gian. Một ngày nọ, người dân Marvelous Land khảo sát các con đường và nhận thấy cần nâng cấp mạng lưới đường hiện có, hoặc xây thêm một số tuyến đường hai chiều. Điều cần quan tâm nhất là tổng thời gian ngắn nhất để đi lại giữa 2 thành phố trung tâm kinh tế. Trước khi quyết định nâng cấp mạng lưới đường đi, cần xác định các tuyến đường trọng yếu là những tuyến đường mà không thể không đi qua khi muốn đi từ thành phố 1 tới thành phố \(N\) với tổng thời gian ngắn nhất.

Yêu cầu: Hãy viết chương trình đếm số lượng tuyến đường trọng yếu.

Input

  • Dòng đầu chứa hai số nguyên \(N\) và \(M\) (\(1 \le N \le 10^5, 1 \le M \le 2 × 10^5\)), số thành phố và số
    tuyến đường.
  • \(M\) dòng tiếp theo, mỗi dòng ghi ba số nguyên, dòng thứ \(i+1\) ghi số \(u_i, v_i, t_i\) (\(1 \le u_i, v_i \le N, 1 \le t_i \le 10^6\)) là các thông tin của tuyến đường thứ \(i\).

Output

  • Ghi ra duy nhất một số nguyên là số tuyến đường trọng
    yếu.

Scoring

  • 50% số điểm của bài tương ứng với các test có \(N \le 1000\) và \(M \le 1000\)

Example

Test 1

Input 
8 9
1 2 3
1 3 1
2 4 4
3 4 7
5 4 9
8 6 5
8 7 4
6 5 2
7 5 3
Output 
3

Bình luận

  • KTGAME • 12:31 a.m. 19 Tháng 8, 2024 • ← chỉnh sửa 4

    Mik đã AC và xin phép gợi ý nha :>

    • Đầu tiên dùng Dijkstra() để tìm đường đi ngắn nhất từ 1->N
    • Sau đó ta dùng DFS() để xây một đồ thị con (đồ thị con gồm các tuyến đường có độ dài thỏa mãn 1->N ngắn nhất)
    • Dùng thuật toán Tarjan() để tìm các cạnh trọng yếu phải đi (Trong thuật toán Tarjan gọi đây là Cầu -> [Bridges])

    • Có 1 lưu ý nhỏ nhưng là phần quan trọng nhất:

      • Bởi vì 1 cặp đỉnh có thể được duyệt nhiều lần nên khi thỏa mãn 1 lần u,v thì v,u cũng thỏa mãn nên ta đưa vào set
        thêm nữa là dùng cặp theo min-max hoặc max-min để đảm bảo không trùng lặp:

      ~ Với Python3 : Bridges.add(( min(u,v), max(u,v) ))
      ~ Với C++ : Bridges.insert({ min(u,v), max(u,v) } )

    • Kết quả cuối cùng là số cặp trong Bridges

    • Trong link này mình có chú thích rồi hãy học và tự code đừng coppy nhé!

    *Độ phức tạp thuật toán:

    • Dijkstra(): O((N+M)log(N))
    • DFS() và Tarjan(): cùng chung O(N+M)
    • Độ phức tạp chi tiết: O(N+((N+M)log(N))+(2(N+M)))
    • Độ phức tạp cao nhất: O((N+M)log(N))
    • Time mình nộp là ~~1.5s

    @_@ Code Python3: https://onlinegdb.com/gOV_wsPF4

    2
    Phản hồi
    • 7 bình luận nữa