[[problem:MOVE]]문제 질문드립니다.

각 지점 및 간선을 인접리스트로 구성하여 너비우선 탐색을 합니다.
그냥 너비 우선 탐색으로 시도 했더니 시간초과가 발생하여..
문제해결전략 책에 나온 양방향 탐색을 시도했습니다.

그런데 부호가 다른 지점에서 어떻게 처리할지를 모르겠네요.
부호가 다르다!라는 시점에서 딱 최소거리가 나오는게 아닌 문제인데..
어떻게 처리 해야 하는지 도움을 구합니다.

~~~ c++
int bfs(int start, int finish)
{
vectordistance = vector(ADJ.size(), 0);
queue q;

best = 987654321;   
distance[start] = 1;
distance[finish] = -1;
q.push(start);
q.push(finish);
while (!q.empty()) {
    int here = q.front();
    q.pop();
    for (int i = 0; i < ADJ[here].size(); i++) {
        Edge there = ADJ[here][i];
        int d = incr(distance[here], there.second);
        if (best <= abs(d)) continue;
        if (distance[there.first] == 0 || distance[there.first] == d) {
            distance[there.first] = d;
            q.push(there.first);
        } else if ((d > 0 && distance[there.first] > d) || (d < 0 && distance[there.first] < d)) {
            distance[there.first] = d;
        }  else if (sgn(distance[here]) != sgn(distance[there.first])) {
            //cout << "HIT - " << best << endl;
            best = min(best, abs(distance[here]) + abs(distance[there.first]) - 2 + abs(there.second));
        }
    }
}

}
~~~