글 읽기 - 골목길 문제 질문입니다.

zzerross 6년 전 0

골목길 문제 (https://www.acmicpc.net/proble...)

이상하게 않풀리네요.

완전 어렵진 않는 거 같은데 아직까지 정답자도 없고, 질답도 별로 없구요.

저도 몇달 전에 못풀고 포기했다가, 다시 풀어보는데도 여전히....답을 못맞추고 있네요....ㅜ.ㅜ

일단 질문은, 지문에서

"그런데, 경우에 따라서는 최적의 경로라는 것이 존재하지 않는 상황이 발생한다."

도착지점에 도달할 수 없는 경우

외에 또 다른 경우가 있을까요?

일단 풀어본 코드는 아래와 같습니다.

일단 간단하게 queue, bfs로

각 지점에서의 최적 결과가 갱신될 때,

ba 배열에 이전에 어디서 왔는지를 저장했습니다.

#include <stdio.h>

#define vs 100
#define es 20000
#define cs 1000
#define cz (vs * cs)

int vn, en, sa[es+1], da[es+1], ca[es+1], ba[vs+1], ra[vs+1];

struct qu {
    int q[es], f, r;

    void rst() {
        f = r = 0;
    }

    bool nil() {
        return f == r;
    }

    void psh(int v) {
        q[r++] = v;
    }

    int pop() {
        return q[f++];
    }
} qu;

int trk(int v) {
    if (v <= 0)
        return 0;

    if (v == 1) {
        printf("%d ", v);

        return 1;
    }

    if (trk(ba[v])) {
        printf("%d ", v);

        return 1;
    }

    return 0;
}

int main() {
    scanf("%d %d", &vn, &en);

    for (int v = 1; v <= vn; v++)
        ba[v] = 0;

    for (int v = 1; v <= vn; v++)
        ra[v] = -cz;

    for (int e = 1; e <= en; e++)
        scanf("%d %d %d", &sa[e], &da[e], &ca[e]);

    qu.rst();
    qu.psh(1);

    ra[1] = 0;

    for (int s, d; !qu.nil();) {
        s = qu.pop();

        for (int e = 1; e <= en; e++) {
            if (s != sa[e])
                continue;

            d = da[e];

            if (ra[d] < ra[s] + ca[e]) {
                ra[d] = ra[s] + ca[e];

                qu.psh(d);

                ba[d] = s;
            }
        }
    }

    if (ba[vn]) {
        trk(vn);
    } else {
        printf("-1\n");
    }

    return 0;
}

atomzeno 6년 전 0

저도 맞은 건 아닌데, 추가적으로 양수 cycle이 있고, 그 cycle위의 정점에서 n번째까지 갈 수 있음 -1인 것 같습니다.

저도 이거 외엔 잘 모르겠네요...9%에서 계속 틀려서

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

문제

문제

출처

ICPC

골목길 문제 질문입니다.

zzerross 6년 전 0

atomzeno 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말