글 읽기 - 왜 이렇게 하면 안되나요? ( 92% 에서 틀립니다. )

zxcv5052 3년 전 0

to == N 이 부분이 왜 안되나요?

92%에서 틀리면 사이클이 있어도 싸이클과 호텔이 연관되지 않아서 틀렸다고 질문 게시판에서 보았는데

to == N을 하게 된다면 사이클이 돌아서 costs[to] 부분을 계속 업데이트 하기 때문에 사이클이 호텔과 연관되어있는 것 아닌가요?ㅠㅠ

static boolean bellmanFod(){
        costs[1] = Long.valueOf(0);
        boolean isCycle = false;
        for(int z=1; z <= N+1; z++){
            for(int i=1; i < N+1; i++){
                for(int k=0; k<ways[i].size(); k++){
                    Way way = ways[i].get(k);
                    int to = way.to;
                    int cost = way.cost;

                    if(costs[i] == Long.MAX_VALUE) continue;
                    if(costs[to] > costs[i] + cost){
                        costs[to] = costs[i] + cost;
                        previous[to][1] = i;
                        if(z==N+1){

                            // this is Cycle.
                            if(to == N){
                                isCycle = true;
                            }
                        }
                    }
                }
            }
        }
        return isCycle;
    }

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

문제

문제

출처

ICPC

왜 이렇게 하면 안되나요? ( 92% 에서 틀립니다. )

zxcv5052 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말