Cạnh Tăng Khoảng Cách Ngắn Nhất
Points
40
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
graph
Đề bài
Cho một mạng giao thông liên thông gồm $N$ nút giao (đánh số từ $1$ đến $N$) và $M$ tuyến đường hai chiều (đánh số từ $1$ đến $M$, có thể có nhiều tuyến nối cùng một cặp nút). Tuyến đường thứ $i$ nối hai nút $u_i, v_i$ và có độ dài $w_i > 0$.
Xét hành trình ngắn nhất từ nút xuất phát $S$ đến nút đích $T$. Một tuyến đường $i$ được gọi là không thể thay thế nếu khi đóng cửa riêng tuyến đường $i$, độ dài đường đi ngắn nhất từ $S$ tới $T$ bị tăng lên thực sự (hoặc không còn đường đi từ $S$ tới $T$).
Hãy tìm tất cả các tuyến đường không thể thay thế và liệt kê chỉ số của chúng theo thứ tự tăng dần.
Dữ liệu vào
- Dòng đầu tiên chứa bốn số nguyên $N, M, S, T$ ($2 \le N \le 10^5$, $1 \le M \le 2 \cdot 10^5$, $1 \le S, T \le N$, $S \ne T$).
- $M$ dòng tiếp theo, dòng thứ $i$ chứa ba số nguyên $u_i, v_i, w_i$ ($1 \le u_i, v_i \le N$, $u_i \ne v_i$, $1 \le w_i \le 10^9$).
Dữ liệu ra
- Dòng đầu tiên in ra số lượng tuyến đường $K$ tìm được.
- Nếu $K > 0$, dòng thứ hai in ra $K$ chỉ số (đánh số từ $1$) theo thứ tự tăng dần, cách nhau bởi dấu cách.
Ví dụ
| Input | Output |
|---|---|
| 5 6 1 5 1 2 1 2 3 2 3 5 2 2 4 2 4 5 2 3 4 1 |
1 1 |
Giới hạn
Thời gian: 1.0s, Bộ nhớ: 256MB.
Community Discussion