안녕하세요. 데이터 관련 요청을 드리고자 합니다.

  • Fate
    Fate

    안녕하세요. 종종 알고스팟에 문제를 푸는 평범한 학생입니다.
    최근 DRUNKEN 문제를 풀어서 제출하는데 WA만 잔뜩 맞고 있습니다.
    코드를 보면서 검증을 계속하고, 다른 그래프를 그려서 발생할 수 있는 상황들도 만들어보았는데 기대했던 값들이 전부 나오고 있습니다.
    그래서 채점에 사용되는 데이터를 받아 어떤 부분을 놓치고 있는지를 보고 싶습니다.
    제가 작성한 코드도 공유차 올려봅니다..

    #include <cstdio>

#define FOR(i,s,e) for(auto (i)=(s);(i)<(e);(i)++)
#define FORE(i,s,e) for(auto (i)=(s);(i)<=(e);(i)++)

const int _N = 501;
const int _MAX = 10101010;
int C[_N][_N];
int A[_N][_N];
int D[_N];

int main()
{
    int V, E;
    scanf("%d %d", &V, &E);
    FORE(i, 1, V) scanf("%d", &D[i]);
    FORE(i, 1, V) FORE(j, 1, V)
    {
        A[i][j] = _MAX;
        C[i][j] = _MAX;
    }
    FORE(i, 1, V)
    {
        A[i][i] = 0;
    }

    FOR(i, 0, E)
    {
        int u, v, c;
        scanf("%d %d %d", &u, &v, &c);
        C[u][v] = c;
        C[v][u] = c;

        A[u][v] = c;
        A[v][u] = c;
    }

    FORE(i, 1, V) FORE(j, 1, V) FORE(k, 1, V)
        if (D[i] <= D[j] && C[k][j] > C[k][i] + C[i][j])
            C[k][j] = C[k][i] + C[i][j];

    FORE(i, 1, V) FORE(j, 1, V) FORE(k, 1, V)
        if (A[i][j] > C[i][k] + C[j][k] + D[k])
            A[i][j] = C[i][k] + C[j][k] + D[k];

    int T;
    scanf("%d", &T);
    while (T--)
    {
        int s, e;
        scanf("%d %d", &s, &e);
        printf("%d\n", A[s][e]);
    }
}
//C[s][e] : s 노드부터 D값이 단조증가하는 형태로 노드를 선택해 e 노드에 도달했을 때의 최소 비용
//A[s][e] : 문제에서 요구하는 s노드부터 e노드까지 가는 최소비용

    만약 데이터를 보내주실 수 있다면 메일 주소도 적어둡니다.
    gg7308@naver.com

    하루빨리 AC받고 싶네요. TT


    10년 전
5개의 댓글이 있습니다.
  • JongMan
    JongMan

    안녕하세요, 온라인 저지에 사용되는 데이터는 공개하지 않는 것을 원칙으로 하고 있습니다. 입력에 주어진 그래프에서 테스트하는 1000개의 정점 쌍중 거의 절반이 틀리게 나오는 것으로 봐서, 접근 방식 자체가 틀린 것 같은데, 소스 코드와 함께 알고리즘 설명을 올려주시면 좀 더 나은 답변을 받으실 수 있을 거라 생각됩니다.


    10년 전 link
  • Fate
    Fate

    D를 노드의 비용으로 정의했고, C[S][E]를 "S에서 시작해 E에 도착하기 위한 최소 비용"으로 정의했습니다. 그런데 문제 특성상 C를 다음과 같이 조건을 걸었습니다.

    • C[S][E] 경로 내에 노드 T가 존재한다면, D[T] <= D[E]를 만족한다.

    존재하지 않는 경우에는 _MAX값이 들어가고, 정의에 의해 C 배열은 다음과 같은 점화식으로 구해졌습니다.

    C[S][E] = min( C[S][E], C[S][T] + C[T][E] )

    그리고 이 때 정답은 다음과 같이 구해집니다.

    A[S][E] = min( A[S][E], C[S][T] + C[E][T] + D[T] )

    그런데 제가 우려하고 있는 부분은 C[S][T]와 C[T][E]가 제대로 구해져있느냐? 하는 부분입니다. 알고리즘과 소스를 보고 잘못된 부분이 있으면 언제든 답변부탁드립니다.


    10년 전 link
  • Kureyo
    Kureyo

    말씀하신대로라면 입력에서 C[u][v]=C[v][u]=c를 취하는 건 어색하네요
    D[u]<D[v]일때 기준으로 C[u][v]=c , C[v][u] = INF로 정의되어야 하지않나요?


    10년 전 link
  • Fate
    Fate

    @Kureyo 제가 생각한건 다음과 같았습니다.
    C[s][e]에 포함된 노드가 순서대로 s, t1, t2, e가 있을 때 D[t1] <= D[t2] <= D[e] 라는 의미였습니다. s를 포함시키지 않았습니다. (문제에서 시작점과 도착점을 고려하지 않기 때문에)


    10년 전 link
  • JongMan
    JongMan

    제가 정확히 이해한 것인지 모르겠는데, 끝점에서의 검사 시간도 상관이 없기 때문에 D[e]는 애초에 문제에서 아무 상관이 없는 것 같고요. 또, t1과 t2가 경로 내에 어느 순서로 오는지와 그들의 검사 시간 순서는 상관이 없는 것 같은데요..


    10년 전 link

  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.