Chào mọi người, em lại gắp khó khăn trong khi làm bài Bidirectional A*, bài làm của em đã chạy đúng kết quả mà bị TLE: 64.00/50.00. Có lẽ, em cứ nghĩ mãi mà ko biết làm sao để speed up lên một tí nữa. Đây là đề bài:
Đây là ví dụ:
Ý tưởng bài giải là tính lại các trọng số của các đoạn thẳng thông qua hàm potential Function như sau:
Trong đó, piF là potential Function của Forward Graph, piR là potential Function của BackWard Graph.
Dùng hàm Potential Euclide như sau:
Khi đó, độ dài đoạn thẳng mới là:
Sau đó, áp dụng Bidirectional Dijsktra cho đoạn thẳng có trọng số mới:
Code của em:
#include "pch.h"
#include <iostream>
#include <cstdio>
#include <cassert>
#include <vector>
#include <queue>
#include <limits>
#include <utility>
#include <cmath>
using namespace std;
// See the explanations of these typedefs and constants in the starter for friend_suggestion
typedef vector<vector<vector<int>>> Adj;
typedef long long Len;
typedef vector<priority_queue<pair<Len, int>, vector<pair<Len, int>>, greater<pair<Len, int>>>> Queue;
const Len infinite = numeric_limits<Len>::max() / 4;
class AStar {
// See the descriptions of these fields in the starter for friend_suggestion
int n_;
Adj adj_;
Adj cost_;
vector<vector<Len>> distance_;
vector<vector<double>> distWithPotential_;
vector<int> workset_;
vector<bool> visited_;
// Coordinates of the nodes
vector<pair<Len, Len>> xy_;
public:
AStar(int n, Adj adj, Adj cost, vector<pair<Len, Len>> xy)
: n_(n), adj_(adj), cost_(cost), distance_(2, vector<Len>(n_, infinite)), distWithPotential_(2, vector<double>(n_, infinite)), visited_(n), xy_(xy)
{
}
// See the description of this method in the starter for friend_suggestion
void clear() {
for (int i = 0; i < workset_.size(); ++i) {
int v = workset_[i];
distance_[0][v] = infinite;
distance_[1][v] = infinite;
distWithPotential_[0][v] = infinite;
distWithPotential_[1][v] = infinite;
visited_[v] = false;
}
workset_.clear();
}
double potentialFunction(pair<int, int> curr, pair<int, int> s, pair<int, int> t)
{
return (sqrt(pow(t.first - curr.first,2) + pow(t.second - curr.second,2)) - sqrt(pow(s.first - curr.first,2) + pow(s.second- curr.second,2))) / 2;
}
// See the description of this method in the starter for friend_suggestion
void visit(Queue& q, int side, int v, double fakedist) {
// Implement this method yourself
if (distWithPotential_[side][v] == infinite)
{
q[side].push(make_pair(fakedist, v));
workset_.push_back(v);
return;
}
queue<pair<double, int>> tempQueue;
while (!q[side].empty())
{
pair<double, int> curr = q[side].top();
q[side].pop();
if (curr.second == v)
{
curr.first = fakedist;
q[side].push(curr);
workset_.push_back(v);
break;
}
tempQueue.push(curr);
}
while (!tempQueue.empty())
{
q[side].push(tempQueue.front());
tempQueue.pop();
}
}
// Returns the distance from s to t in the graph.
Len query(int s, int t) {
if (s == t) return 0;
clear();
Queue q(2);
visit(q, 0, s, 0);
visit(q, 1, t, 0);
// Implement the rest of the algorithm yourself
distance_[0][s] = 0;
distance_[1][t] = 0;
distWithPotential_[0][s] = 0;
distWithPotential_[1][t] = 0;
Len result = infinite;
while (!q[0].empty() && !q[1].empty())
{
// dijsktra on forward graph
pair<Len, int> currentFor = q[0].top();
int current = currentFor.second;
q[0].pop();
for (int i = 0; i < adj_[0][currentFor.second].size(); i++)
{
int neighbour = adj_[0][current][i];
double lWithPotetial = cost_[0][current][i] - potentialFunction(xy_[current], xy_[s], xy_[t]) + potentialFunction(xy_[neighbour], xy_[s], xy_[t]);
double fakedist = lWithPotetial + distWithPotential_[0][current];
if (fakedist < distWithPotential_[0][neighbour])
{
Len realdist = distance_[0][current] + cost_[0][current][i];
visit(q, 0, neighbour, fakedist);
distance_[0][neighbour] = realdist;
distWithPotential_[0][neighbour] = fakedist;
}
}
//update result
if (result > distance_[0][current] + distance_[1][current])
result = distance_[0][current] + distance_[1][current];
// check if currentFor is visited
if (visited_[current] == false)
visited_[current] = true;
else
break;
// dijsktra on reverse graph
pair<Len, int> currentBack = q[1].top();
q[1].pop();
current = currentBack.second;
for (int i = 0; i < adj_[1][current].size(); i++)
{
int neighbour = adj_[1][current][i];
double lWithPotential = cost_[1][current][i] - potentialFunction(xy_[current], xy_[t], xy_[s]) + potentialFunction(xy_[neighbour], xy_[t], xy_[s]);
double fakedist = lWithPotential + distWithPotential_[1][current];
if (fakedist < distWithPotential_[1][neighbour])
{
Len realdist = distance_[1][current] + cost_[1][current][i];
visit(q, 1, neighbour, fakedist);
distance_[1][neighbour] = realdist;
distWithPotential_[1][neighbour] = fakedist;
}
}
// update result
if (result > distance_[0][current] + distance_[1][current])
result = distance_[0][current] + distance_[1][current];
// check if currentback is visited
if (visited_[current] == false)
visited_[current] = true;
else
break;
}
if (result == infinite)
return -1;
return result;
}
};
int main() {
int n, m;
cin >> n >> m;
vector<pair<Len, Len>> xy(n);
for (int i = 0; i < n; ++i) {
int a, b;
cin >> a >> b;
xy[i] = make_pair(a, b);
}
Adj adj(2, vector<vector<int>>(n));
Adj cost(2, vector<vector<int>>(n));
for (int i = 0; i < m; ++i) {
int u, v, c;
cin >> u >> v >> c;
adj[0][u - 1].push_back(v - 1);
cost[0][u - 1].push_back(c);
adj[1][v - 1].push_back(u - 1);
cost[1][v - 1].push_back(c);
}
AStar astar(n, adj, cost, xy);
int t;
cin >> t;
for (int i = 0; i < t; ++i) {
int u, v;
cin >> u >> v;
cout << astar.query(u - 1, v - 1) << endl;
}
}
Code em có 1 cái kỳ kỳ là, thay vì dùng hàm pow, em nhân 2 số lại với nhau thì speed up thêm 1 tí nữa, mà khi làm vậy thì sai test case 6/9. Còn dùng hàm pow thì TLE ở test case 8/9. Em không biết làm sao để speed up thêm nữa, em sắp give up rồi, mọi người em và góp ý giúp em với. Em xin cảm ơn nhiều!!
Nếu sau cùng đều push vào 
forward check visited của forward, backward check visited của backward :V :V :V
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?