Hello, I'm trying to solve this problem Link. The problem statement is available in LiveArchive in English.

In the Brazilian SPOJ, the time-limit is quite strict, as the problem resumes to a grid shortest path, I choose the A* algorithm, which generally is faster than Djikstra and it's heuristics fits perfectly in 2-dimensional grids, but my solution isn't fast enough. How can I optimize more the A* ? The current code is:

struct MyLess {
    bool operator () (int x, int y) {
        return f[x] > f[y];
    }
};

int func (void) {
    int i, j;

    dist[conv(RF,CF)] = 0;
    vis[conv(RF,CF)] = 0;

    priority_queue<int, vector<int>, MyLess> q;

    q.push(conv(RF, CF));

    for ( ; !q.empty(); ) {
        int now = q.top(); q.pop();

        if (vis[now]) {
            continue;
        }

        vis[now] = 1;

        if (now == conv(RT, CT)) return dist[now];

        pair<int, int> od = rev(now);

        for (i = 0; i < 24; i++) {
            int ni = od.first + dx[i];
            int nj = od.second + dy[i];

            int next = conv(ni, nj);

            if (ni <= 0 || nj <= 0 || ni > R || nj > C || graph[next] == 1 || vis[next]) continue;

            if (next >= 0 && next < R * C) {
                int next_cost = dist[now] + ct[i];
                int heuristic = abs(ni - RT) + abs(nj - CT);

                if (next_cost < dist[next]) {
                    dist[next] = next_cost;
                    f[next] = heuristic + next_cost;
                    q.push(next);
                }

            }
        }
    }
    return dist[conv(RT,CT)];
}