Đường đi ngắn thứ hai

General
Points
48
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
dp
Submissions
Đề 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$
Draft saved