NEWBUS 관련 질문드립니다 kun452 안녕하세요 NEWBUS를 풀었는데 계속 오답이 떠서 질문드립니다 최단거리를 구하기 위해 다이스트라 알고리즘을 사용하였는데요 여기서 dist배열의 값을 갱신시켜줄 때 방문했던거와 관련없이 현제 start에서의 값이 더 작다면 dist배열을 바꿔주고 같으면 NUM배열을 하나 증가 크면 넘어가도록 하였는데 뭐가 잘못됬는지 잘 모르겠네요... #include <iostream> #include <algorithm> #include <vector> #include <string> using namespace std; void Dijstra(int **A, int N, int start, int *NUM, int *dist){ int *visited = new int[N+1]; for(int j=0; j<=N; j++){ dist[j] = 987654321; NUM[j] = 0; visited[j] = 0; } dist[start] = 0; NUM[start] = 0; visited[start] = 1; for(int j=1; j<=N; j++){ if(A[start][j] != 987654321){ dist[j] = A[start][j]; NUM[j]++; } } int num = 1; while(num < N){ num++; int MIN = 987654322; int min_index; for(int j=1; j<=N; j++){ if(!visited[j] && dist[j] < MIN){ MIN = dist[j]; min_index = j; } } start = min_index; visited[start] = 1; for(int j=1; j<=N; j++){ if(dist[start] + A[start][j] < dist[j]){ dist[j] = dist[start] + A[start][j]; NUM[j] = 1; }else if(dist[start] + A[start][j] == dist[j]){ NUM[j] ++; }else{ continue; } } } } int main(){ int num; cin >> num; for(int i=0; i<num; i++){ int N, line, Q; cin >> N >> line >> Q; int **A = new int*[N+1]; for(int j=0; j<=N; j++){ A[j] = new int[N+1]; for(int k=0; k<=N; k++){ A[j][k] = 987654321; } } int a, b, w; for(int j=0; j<line; j++){ cin >> a >> b >> w; A[a][b] = w; A[b][a] = w; } int *NUM = new int[N+1]; int *dist = new int[N+1]; for(int j=0; j<Q; j++){ cin >> a >> b; Dijstra(A, N, a, NUM, dist); if(NUM[b] == 0) cout << "no" << endl; if(NUM[b] == 1) cout << "only" << endl; if(NUM[b] >= 2) cout << "many" << endl; //cout << NUM[b] << endl; } } return 0; } 9년 전
5개의 댓글이 있습니다. hyunhwan 우선 new를 사용해 동적 메모리를 사용 한 다음에 해제를 하지 않은 부분이 보이는데, 이 부분도 문제의 소지가 있는 것 같습니다. 9년 전 link kun452 혹시 visited배열 말씀하기는건가요? 9년 전 link kun452 visited배열을 다른배열처럼 바깥으로빼도 오답으로 뜨네요;; 9년 전 link JongMan 이런 그래프를 상상해 보세요: a - b - d - e \ / c 시작점은 a, 종착점은 e입니다. 9년 전 link kun452 아 감사합니다... 맨날 하나씩 잘 못보는 것 같네요ㅠㅠ 그걸 생각하고 풀어보니 바로 해결됬습니다^^ 9년 전 link 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
kun452
안녕하세요 NEWBUS를 풀었는데 계속 오답이 떠서 질문드립니다
최단거리를 구하기 위해 다이스트라 알고리즘을 사용하였는데요 여기서 dist배열의 값을 갱신시켜줄 때 방문했던거와 관련없이 현제 start에서의 값이 더 작다면 dist배열을 바꿔주고 같으면 NUM배열을 하나 증가 크면 넘어가도록 하였는데 뭐가 잘못됬는지 잘 모르겠네요...
9년 전