MOVE 문제 질문드립니다! sancho MOVE문제 질문드립니다. 각 지점 및 간선을 인접리스트로 구성하여 너비우선 탐색을 합니다. 그냥 너비 우선 탐색으로 시도 했더니 시간초과가 발생하여.. 문제해결전략 책에 나온 양방향 탐색을 시도했습니다. 그런데 부호가 다른 지점에서 어떻게 처리할지를 모르겠네요. 부호가 다르다!라는 시점에서 딱 최소거리가 나오는게 아닌 문제인데.. 어떻게 처리 해야 하는지 도움을 구합니다. int bfs(int start, int finish) { vector<int>distance = vector<int>(ADJ.size(), 0); queue<int> 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)); } } } } 8년 전
1개의 댓글이 있습니다. sancho 책에 나온 다익스트라 알고리즘을 적용하니 바로 pass 되네요;; 너비우선탐색 및 양방향 탐색으로도 가능할 것 같은데 ㅠㅠ 8년 전 link 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
sancho
MOVE문제 질문드립니다.
각 지점 및 간선을 인접리스트로 구성하여 너비우선 탐색을 합니다.
그냥 너비 우선 탐색으로 시도 했더니 시간초과가 발생하여..
문제해결전략 책에 나온 양방향 탐색을 시도했습니다.
그런데 부호가 다른 지점에서 어떻게 처리할지를 모르겠네요.
부호가 다르다!라는 시점에서 딱 최소거리가 나오는게 아닌 문제인데..
어떻게 처리 해야 하는지 도움을 구합니다.
8년 전