Pictures collection #2
- Get link
- X
- Other Apps
Madrid, Spain
SPOJ - QBSCHOOL
Link: https://codeforces.com/group/FLVn1Sc504/contest/274518/problem/W Tags: dp, dijkstra, shortest path Difficulty: ez++ Tóm tắt: Cho đồ thị gồm n đỉnh đánh số từ 1 đến n. Cần tìm tổng số đường đi ngắn nhất từ 1 đến n. Ý tưởng: Sử dụng thuật toán dijkstra tìm đường đi ngắn nhất như bình thường, tuy nhiên ta đặt thêm mảng dp[i] với ý nghĩa dp[i] là số đường đi ngắn nhất từ đỉnh 1 đến đỉnh i. Ta vừa dijkstra vừa update như sau: Giả sử ta đang ở đỉnh u và đỉnh tiếp theo là v, và trọng số cạnh giữa u và v là w: Nếu dist[v] > dist[u] + w thì dist[v] = dist[u] + w và dp[v] = dp[u] Nếu dist[v] == dist[u] + w thì dp[v] += dp[u] Khởi tạo dp[1] = 1 vì luôn có 1 đường đi từ đỉnh 1 đến chính nó. Code: https://ideone.com/XxdyLB
hình đẹp quá bis bis
ReplyDeletenhưng linyõu đẹp hơn
ReplyDeletelinyou gì bạn ơi, ngta là nhà khoa học mà
ReplyDelete