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