Cạnh Tăng Khoảng Cách Ngắn Nhất

Buổi 44 — Cầu & Khớp Graphs
Points
40
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
graph
Submissions
Đề 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.

Draft saved