Đường đi ngắn thứ hai
Points
48
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
dp
Đề bài
Cho đồ thị vô hướng gồm $N$ đỉnh và $M$ cạnh có trọng số dương $w$. Một đường đi từ $1$ đến $N$ được phép đi qua một đỉnh hoặc một cạnh nhiều lần. Hãy tìm độ dài nhỏ thứ hai (nghiêm ngặt lớn hơn độ dài đường đi ngắn nhất) của đường đi từ $1$ đến $N$. Nếu không tồn tại (chẳng hạn không có đường đi hoặc mọi đường đi đều có cùng độ dài), in ra -1.
Đề bài
Trường học có $N$ học sinh và $K$ câu lạc bộ (CLB). CLB thứ $j$ chỉ tiếp nhận tối đa $cap_j$ học sinh.
Mỗi học sinh $i$ đánh giá mức độ không hài lòng khi vào CLB $j$ là $C_{i,j}$ (hoặc -1 nếu học sinh đó từ chối vào CLB $j$). Mỗi học sinh chỉ được tham gia tối đa 1 CLB.
Hãy phân bổ sao cho số học sinh được vào CLB là nhiều nhất, và trong số các cách phân bổ đó, tổng mức độ không hài lòng là nhỏ nhất.
Dữ liệu vào
- Dòng đầu tiên chứa hai số nguyên $N, K$ ($1 \le N \le 200, 1 \le K \le 50$).
- Dòng thứ hai chứa $K$ số nguyên $cap_1, \dots, cap_K$ ($0 \le cap_j \le N$).
- $N$ dòng tiếp theo, mỗi dòng chứa $K$ số nguyên $C_{i,j}$ ($C_{i,j} = -1$ hoặc $0 \le C_{i,j} \le 10^5$).
Dữ liệu vào
- Dòng đầu chứa hai số nguyên $N, M$ ($1 \le N \le 10^5$, $0 \le M \le 2 \cdot 10^5$).
- $M$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $u, v, w$ ($1 \le u, v \le N$, $1 \le w \le 10^9$).
Dữ liệu ra
- Một số nguyên duy nhất là độ dài đường đi ngắn thứ hai, hoặc
-1.
Ví dụ
| Input | Output |
|---|---|
| 4 4 1 2 100 2 4 200 2 3 250 3 4 100 |
450 |
| 2 0 | -1 |
Giới hạn
- $1 \le N \le 10^5$, $0 \le M \le 2 \cdot 10^5$
- $1 \le w \le 10^9$
Community Discussion