글 읽기 - [2주째...] 1005번 제발 도와주세요. 틀린 부분이 어딘지 감이 안와요.

lian 8년 전 1

시작지점이 여러개인 부분도 해봤는데, 잘 되는거 같거든요 ㅠ?

테스트 케이스도 여러개 만들어서 돌려도 봤는데 안되더라구요

소스코드 작성한 방식은,

dept가 departure, dest가 destination을 의미하구요. 즉 dept 가 x이고 dest가 y입니다.

여기서 x, y를 입력받을 때 큐에다가 저장했구요, q[x] = y 형태로 저장했습니다. 즉, dept값 알고 있으면 어디로 향하는지 알게되는거죠.

그리고 입력받을때 isDept라는 boolean 변수로 출발노드가 어디인지 알아내는데 썼습니다.

출발노드를 알고 난 다음에는 cost값이 0인 가상의 노드를 하나 만들어서 그 출발점과 이어져 있는 것처럼 만들어줬어요.

예를들어서 1 - 2 - 5 - 3 - 4 이런식으로 연결되어있는데 w를 5로 지정하면 출발노드가 1, 4잖아요? 이걸 0번 노드가 1, 4도 연결하고 있다고 봤어요.

그럼 항상 시작노드는 0이 되니까...

calc라는 재귀함수를 만들어서 calc(0)를 호출하면

거기서부터 재귀함수가 w까지 거슬러 올라가면서 각각의 노드부터 w까지의 거리를 fromNODEtoW라는 배열변수에다가 저장합니다.

일단 제가 20개 정도 만들어본 테스트 케이스에서는 전부 동작을 하는데,

채점 50%에서 돌아가지가 않습니다. ㅠ;

답변좀 부탁드려요.

#include <stdio.h>
#include <string.h>
#include <queue>
using namespace std;

int t, n, k;
int i, j;
int x, y, w;
int cost[1001];
bool isDept[1001];
int fromNODEtoW[1001];
queue<int> q[100001];

//recursive function
int calc( int dept ) {
    int dest, tempCost;
    bool everEntered = false;
    
    while(!q[dept].empty()) {
        everEntered = true;
        dest = q[dept].front();
        q[dept].pop();
        
        tempCost = cost[dept] + ((fromNODEtoW[dest] == -1)? calc(dest) : fromNODEtoW[dest]);
        if(fromNODEtoW[dept] < tempCost || fromNODEtoW[dept] == -1) fromNODEtoW[dept] = tempCost;
    }
    
    if(everEntered) {
        return fromNODEtoW[dept];
    }
    else { //base case
        fromNODEtoW[w] = cost[w];
        return fromNODEtoW[w];
    }
}

int main() {
    scanf("%d", &t);
    while(t--) {
        //initialization
        memset(cost, 0, sizeof(cost));
        memset(isDept, true, sizeof(isDept));
        memset(fromNODEtoW, -1, sizeof(fromNODEtoW));
        
        scanf("%d", &n);        
        scanf("%d", &k);
        
        for(i=1; i<n+1; i++) {
            scanf("%d", &cost[i]);
        }
        for(i=1; i<k+1; i++) {
            scanf("%d %d", &x, &y);
            isDept[y] = false;
            q[x].push(y);
        }
        for(i=1; i<n+1; i++) {
            if(isDept[i]) {
                q[0].push(i);
            }
        }
        
        scanf("%d", &w);
        printf("%d\n", calc(0));
    }
    return 0;
}

ntopia 8년 전 1

1
3 2
100 100 100
1 2
2 3
1

이 데이터는 답이 100 아닌가요? 소스를 돌려보니 300이 나오네요

lian 8년 전 9

아.. 드디어 풀었네요 ㅠ

이 질문글 보시는 분들을 위해 테스트 케이스 올려볼게요.

19
3 2
100 100 100
1 2
2 3
1
3 2
100 100 100
1 2
2 3
2
11 10
10 100 1 1 1 5 8 9 7 1000 10
1 2
2 3
3 4
4 5
5 6
6 7
5 8
8 9
10 11
11 3
3
11 10
10 100 1 1 1 5 8 9 7 1000 10
1 2
2 3
3 4
4 5
5 6
6 7
5 8
8 9
10 11
11 3
4
11 10
10 100 1 1 1 5 8 9 7 1000 10
1 2
2 3
3 4
4 5
5 6
6 7
5 8
8 9
10 11
11 3
6
4 4
10 1 100 10
1 2
1 3
2 4
3 4
4
8 8
10 20 1 5 8 7 1 43
1 2
1 3
2 4
2 5
3 6
5 7
6 7
7 8
7
10 11
10 1 1 100 10 10 100 1 1 1
1 2
2 3
3 6
4 3
4 7
4 9
5 4
6 9
7 8
8 9
10 7
9
5 4
10 1 100 10 1000
5 2
1 3
2 4
3 4
4
7 6
1 100 10 1000 10 1 1
1 2
2 3
3 7
4 5
5 6
6 7
7
7 6
1 10 1 100 1 5 8
1 2
2 3
4 5
5 3
3 6
3 7
3
7 6
1 10 1 100 1 5 8
1 2
2 3
4 5
5 3
3 6
3 7
7
5 3
1 3 10 10 5
1 4
2 3
3 5
2
5 3
1 3 10 10 5
1 4
2 3
3 5
3
5 3
1 3 10 10 5
1 4
2 3
3 5
5
5 3
1 3 10 10 5
1 4
2 3
3 5
4
5 3
1 3 10 10 5
1 4
2 3
3 5
1
2 1
10
5
2 1
2
2 1
10
5
2 1
1

답은

100
200
1011
1012
1018
120
39
212
1011
1012
102
110
3
13
18
11
1
5
15

입니다.

이거 다 맞는데도 틀렸다고 뜨면, 초기화 문제더라구요 ㅠ

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

[2주째...] 1005번 제발 도와주세요. 틀린 부분이 어딘지 감이 안와요.

lian 8년 전 1

ntopia 8년 전 1

lian 8년 전 0

lian 8년 전 9

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말