Anh viết thiếu input kìa :v, tọa độ xy nữa.
Speed Up Bidirectional A* Algorithm
cái này Dijkstra mà :V à cho bài Dijkstra cũ ấy, chắc post lộn thớt A* này rồi :V
thử coi xài pq kiểu kia có được ko :V anh nhớ hồi đó chạy đúng mà =]]
bài input này nè
5 20
1 2 667
1 3 677
1 4 700
1 5 622
2 1 118
2 3 325
2 4 784
2 5 11
3 1 585
3 2 956
3 4 551
3 5 559
4 1 503
4 2 722
4 3 331
4 5 366
5 1 880
5 2 883
5 3 461
5 4 228
10
1 1
1 2
1 3
1 4
1 5
2 1
2 2
2 3
2 4
2 5
Output:
0
667
677
700
622
118
0
325
239
11
1 Like
Anh làm sai rồi, điều kiện infinity = -1 đâu :v
à nó bắt unreachable thì trả về -1 à :V
vậy sửa dòng return trong distBidirectionalDijkstra là được:
// thêm constant mới:
const Weight kInfinite = std::numeric_limits<Weight>::max();
const Weight kUnreachable = -1; // mới
...
return q.empty() || qR.empty() ? kUnreachable : bestDistSoFar; // kUnreachable thay vì kInfinite
2 Likes
Bài của anh đúng rồi nha 12.06/25s, đọc ko hiểu gì hết trơn :v c++ nhưng sao cú pháp nhìn lạ quá.
12 giây lận à 
à chắc tại tạo mới visited mỗi lần query :V nhưng mà thử để biết xài pq kiểu kia ngon lành mà :V
3 Likes
lười tạo class có thêm cái workset_ để clear() quá =] mà cái q kia chỉnh lại đúng mà :V Em chỉnh từ từ đi =]
a code kiểu “làm biếng” :V Tái sử dụng code của Dijkstra cho Bidirectional Dijkstra. Đọc giải thích thấy nó chỉ khác ở chỗ breakPrecondition là dist[q.top()] + distR[qR.top()] >= bestDistSoFar và mỗi lần process neighbor thì có thêm hàm updateBestDist nếu neighbor v đã được dijkstra đối diện visited thì update bestDistSoFar. Còn lại giống hết :V
2 Likes
Có nhiều chỗ em chưa hiểu lắm. Anh tạo min pq thế nào vậy? Với lại, sao anh lại dùng c++ 17, có phải nó dễ dùng và sau này đi làm dễ hơn ko.
minpq của a chỉ chứa Vertex, ko chứa cặp (Weight, Vertex). Vì ko có thông tin về weight của vertex để so sánh nên phải tạo hàm so sánh riêng, sử dụng giá trị trong vector dist để so sánh:
// vector chứa dist của các vertices
std::vector<Weight> dist(n, kInfinite);
// hàm so sánh vertex u và vertex v dựa trên giá trị dist[u] và dist[v]
auto vertexWeightComp = [&](Vertex u, Vertex v) { return dist[u] > dist[v]; };
// ^dấu & nghĩa là lambda này có capture biến bên ngoài theo reference, ở đây là vector dist
// tạo pq sử dụng hàm so sánh trên :V
std::priority_queue<Vertex, std::vector<Vertex>, decltype(vertexWeightComp)> q(vertexWeightComp);
// ^kiểu pq chứa ^kiểu comparator ^vì comparator này có capture biến ngoài (ở đây là vector dist) nên phải thêm object comparator đã capture biến ngoài vào :V
// ^kiểu thùng chứa của pq, ở đây xài mặc định vector
//
hên xui =] ko biết kiểu này có lẹ hơn là xài cặp (Weight, Vertex) ko, phải chạy thử mới biết :V nhưng thuật toán Dijkstra trên wiki thấy nó ghi vậy =]]
u ← vertex in Q with min dist[u]
3 Likes
Bài này C++17 chắc chỉ dùng mỗi chỗ unpacking pair 
4 Likes
đương nhiên là code dễ hơn :V Trong C++ dỏm hàm chỉ return được 1 giá trị. Trong C++ xịn hàm có thể return bao nhiêu giá trị cũng được, nhờ std::pair với 2 giá trị hoặc std::tuplenếu nhiều hơn 2 giá trị. Ví dụ cái hàm readGraph trả về 2 giá trị adj và adjW. C++ dỏm cũng làm được điều này, nhưng khi nhận lấy giá trị trả về thì code rất là xấu:
auto p = readGraph(...);
auto& adj = p.first; // & để tránh copy
auto& adjW = p.second; // & để tránh copy
// tự dưng thừa ra biến p, pollute namespace, ko đặt tên biến khác là p được nữa :V:V:V
hoặc xài std::tie
AdjacentList adj; // phải viết kiểu của adj ra :V
AdjacentWeightList adjW; // phải viết kiểu của adjW ra :V
//...
// 10 dòng nữa chắc chết :V:V
//...
std::tie(adj, adjW) = readGraph(...); // 1 dòng gọn nhẹ
với C++17 có structural binding hay gì đó a quên tên rồi =] có thể viết phát như vậy luôn:
auto [adj, adjW] = readGraph(...); // khỏi cần & hay p hay kiểu của abcxyz gì hết.
ko xài ở đây nhưng for loop cho map, unordered_map cũng dễ hơn nhiều
for (auto& [k, v] : mymap) { // code cứ như Python ấy
...
}
3 Likes
Chắc là em phải dành thêm nhiều thời gian nữa thì mới hiểu hết được. Chứ giờ em cũng không biết sửa kiểu gì luôn, tại em không hiểu gì hết. Cảm ơn anh nhiều lắm. i appreciate your help!
em ko hiểu code anh cũng được, tìm cách sửa code chỗ q kia lại là được mà :V
3 Likes
Sr anh, em không đủ giỏi đến vậy.
từ từ lên level :V mà đúng 8/9 test cases cũng pass rồi mà =]
2 Likes
Ahihi, axxx 8/9 là chưa đạt, em không thể tự an ủi mình như vậy được, em thấy 3 bài cuối chua lắm, 2 bài mà em giải gần 1 tuần rồi, boo hoo.
1 Like
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?