Đường đi ngắn nhất
40 bài đường đi ngắn nhất, độ khó tăng dần (rating 900 đến 2400): Dijkstra và truy vết, đếm số đường đi ngắn nhất, k đường đi ngắn nhất, Dijkstra trên đồ thị trạng thái và đồ thị phân tầng, DAG đường đi ngắn nhất, Bellman-Ford và chu trình âm, Floyd-Warshall.
Đề bài
40
Mã
Tên
Nhóm
Độ khó
Điểm
% AC
# AC
shortroute1
Điểm1,00
Đường Đi Ngắn Nhất I
Dijkstra cơ bản với hàng đợi ưu tiên
Chưa phân loại
Tỷ lệ AC
100,0%
AC
3
shortroute2
Điểm1,00
Đường Đi Ngắn Nhất II
Floyd-Warshall, trả lời truy vấn mọi cặp
Chưa phân loại
Tỷ lệ AC
100,0%
AC
3
rblock14
Điểm1,00
Chặn đường
Nhân đôi cạnh trên đường ngắn nhất, Dijkstra lại
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
vacation
Điểm1,00
Lập Kế Hoạch Du Lịch
Floyd-Warshall, ghép qua trạm trung chuyển
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
flightdiscount
Điểm1,00
Chuyến Bay Giảm Giá
Dijkstra trạng thái (đỉnh, đã dùng phiếu)
Chưa phân loại
Tỷ lệ AC
66,7%
AC
2
gr06_route
Điểm4,00
Lộ trình ngắn nhất
Dijkstra + truy vết đường đi
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
cyclefind
Điểm1,00
Tìm Chu Trình Âm
Bellman-Ford tìm và in chu trình âm
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
highscore
Điểm1,00
Điểm Số Cao Nhất
Bellman-Ford đường dài nhất, chu trình dương
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
investigation
Điểm1,00
Điều Tra
Dijkstra đếm số đường, ít và nhiều cạnh nhất
Chưa phân loại
Tỷ lệ AC
66,7%
AC
2
flightroutes
Điểm1,00
Các Tuyến Bay
Dijkstra lấy mỗi đỉnh k lần, k đường ngắn nhất
Chưa phân loại
Tỷ lệ AC
100,0%
AC
2
gpsduel
Điểm1,00
Hai GPS Đối Đầu
Dijkstra ngược xác định cạnh tốt, Dijkstra lần ba
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
icpc25_mt_l
Điểm4,00
Phố đèn đỏ
Gắn trọng số đỉnh vào cạnh rồi Dijkstra
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
gr06_onpath
Điểm5,00
Cung trên đường ngắn nhất
DAG đường đi ngắn nhất: ds(u)+w+dt(v)=D
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
gr07_fuel
Điểm5,00
Đổ xăng
Dijkstra trạng thái (thành phố, lượng xăng)
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
gr08_closure
Điểm5,00
Bao đóng bắc cầu
Bao đóng bắc cầu Warshall bằng bitset
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
hp_tst_25_b
Điểm5,00
GRAPH
Minimax bằng DSU rồi Dijkstra trên đồ thị con
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
gr07_portal
Điểm5,00
Cổng dịch chuyển
Đỉnh ảo cho mạng dịch chuyển
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
gr07_toall
Điểm5,00
Bệnh viện gần nhất
Dijkstra đa nguồn trên đồ thị đảo
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
gr08_remove
Điểm5,00
Xóa dần các đỉnh
Floyd ngược thời gian: thêm dần đỉnh
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
voi13_tours
Điểm5,00
Hành trình du lịch
Chu trình ngắn nhất qua mỗi đỉnh
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
algorace
Điểm6,00
Đua xe AlgoRace
Floyd cho từng xe + DP số lần đổi xe
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
voi17_metro
Điểm6,00
Tàu điện ngầm
Dijkstra với trạng thái là tuyến đường
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
voi24_impev
Điểm6,00
Cải thiện đánh giá
Hai lần Dijkstra + đếm miền trội bằng Fenwick
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
dhbb25_dx06_11_rain
Điểm6,00
Nước mưa
Dijkstra minimax từ biên, mực nước đọng
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
volley
Điểm6,00
Bóng Chuyền
Dijkstra hai tầng: bán kính taxi rồi chi phí
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
hanam_tst_24_c
Điểm6,00
Khảo cổ
Dijkstra phân tầng theo số lần dùng cổng
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
pt_tst_26_f
Điểm6,00
Trò chơi
Dijkstra biến thể với điều kiện chờ trạm phát
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
dl_tst_26_c
Điểm7,00
Tuyến xe bus
DAG đường ngắn nhất + DP (Commuter Pass)
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
jzzhucity
Điểm7,00
Đóng tuyến đường sắt
Dijkstra, đếm tuyến sắt thừa
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
sptmin
Điểm7,00
Cây đường đi ngắn nhất nhỏ nhất
Cây đường đi ngắn nhất có tổng trọng số nhỏ nhất
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
gl_tst_25_b
Điểm7,00
Xây dựng tuyến đường giao thông
Cập nhật Floyd O(n^2) khi thêm cạnh
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
coloredge
Điểm7,00
Đường đi cạnh màu không giảm
Dijkstra trạng thái (đỉnh, màu) màu không giảm
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
presroad
Điểm8,00
Tổng thống và những con đường
Cạnh trên mọi đường ngắn nhất: đếm số đường
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
kthspath
Điểm8,00
Đường đi ngắn nhất thứ K
Chỉ giữ k cạnh nhỏ nhất, Floyd trên đồ thị nhỏ
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
compgraph
Điểm8,00
Hoàn thiện đồ thị
Gán trọng số cạnh tự do để đường ngắn nhất bằng L
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
minpath
Điểm8,00
Đường đi nhỏ nhất
Dijkstra phân tầng (đã trừ max, đã cộng min)
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0