백준 Java 16707번 American Tour

American Tour 성공출처분류

시간 제한메모리 제한제출정답맞은 사람정답 비율

1 초

256 MB

249

32

27

32.927%

www.acmicpc.net/problem/16707

16707번: American Tour

사용알고리즘

벨만포드

착안점 : 

1->2 까지 최단경로 구하기
2->N까지 최단경로 구하기 

다만, 여기서 1번에서 2번으로 갔던길을 2번에서 N번까지 돌아가지 못한다.
그러므로 1번에서 2번으로 갔던길을 역추적하여 역방향으로 돌리며, 음수로 변경
( 코드상에선 삭제 후 반대로 가는길에 음수를 곱한다.)

일부케이스 예외처리로 N->2번으로 조회

요약
1->2 벨만포드
1->2 경로 모두 역방향 음수변경
N->2 벨만포드

요약코드

        long x = belman(1, 2);
        
        int st = 2;
        while(true){
            
            int ed = p[st][0];
            int mid = 0;
            
//            st :2-> ed: 3
            for (Node ne : list[ed]) {
                if(ne.i%M == p[st][1]%M){
                   list[ed].remove(ne);
                   break;
                }
            }
            for (Node ne : list[st]) {
                if(ne.i%M == p[st][1]%M){
                    ne.w = -ne.w;
                    break;
                }
            }
            if(ed == 1) break;
            st = ed;
        }
        x += belman(N, 2);
        System.out.println(x);

벨판포드

    static long belman(int st, int ed) {
        
        Arrays.fill(d, INF);
        d[st] = 0;
        for (int idx = 1; idx < N; idx++) {
            for (int now = 1; now <= N; now++) {
                
                for (Node ne : list[now]) {
                    int next = ne.y;
                    long next_w = ne.w;
                    //next 갱신
                    if (d[now] != INF && d[now] + next_w < d[next]) {
                        d[next] = d[now] + next_w;
                        p[next][0] = now;
                        p[next][1] = ne.i;
                    }
                }
            }
        }
        return d[ed];
    }