Nâng cấp đường (OLP 10 - 2019)
Xem PDFHà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 3Output
3
Bình luận
Cách 4:
Tạo đồ thị dijkstra
Giao các đường đi dijkstra lại với nhau nén lại thành 1 và đánh dấu
Những cạnh chưa được đánh dấu là cạnh cần tìm
Cách 3:
Xây đồ thị dựa trên các cạnh là dijkstra
Các cạnh khác có hay không không quan trọng vì chẳng ai thèm đi nên đừng thêm
Đếm số cầu trong đồ thị
Cách 2:
Gọi \(c(u)\) là số đường đi dijkstra từ \(1 \rightarrow u\)
Gọi \(c'(u)\) là số đường đi dijkstra từ \(n \rightarrow u\)
Khi \(c(u) \neq c(v)\) thì \(c(u) = \Sigma(c(v_p))\) nên nó có thể đi bất cứ đường đi dijkstra nào nên ko thỏa mãn, tương tự với \(c'()\)
Nếu \(c(u) = c(v)\) và \(c'(u) = c'(v)\) thì nó là đường đi thỏa mãn
Truy vết một đường đi dijkstra bất kì và kiêm tra điều kiện (vì mọi đường đi dijkstra đều đi qua các đoạn đường cần tìm)
Cách 1:
Xét \(u \rightarrow v_1, v_2, \dots, v_k\)
Nếu \(u \rightarrow v_p\) không phải đường đi nhỏ nhất trong \(1 \rightarrow n\) hoặc \(n \rightarrow 1\) thì ta loại
Nếu có nhiều hơn 1 đường đi \(u \rightarrow v_p\) là đường đi nhỏ nhất tới \(1\) hoặc \(n\) thì ta loại hết các cạnh \(u - v_i\), vì nó đi đường đi dijkstra nào cũng được nên không thỏa mãn
Nếu chỉ có 1 đường đi \(u \rightarrow v_p\) trong cả đường đi nhỏ nhất tới \(1\) hoặc \(n\) thì ta giữ