Random pics #3 - wandering clouds

★ Taken on Dec 21, 2020 - exactly two years since the day I started to learn programming ★




A student who loves reading, writing, and coding. Currently doing a Bachelor's degree in Artificial Intelligence at FPT University. Please go to the "About me" section to find more information.

Comments

Post a Comment

Popular posts from this blog

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
Read more