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

  • User Avatar
    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


    11년 전
5개의 댓글이 있습니다.
  • User Avatar
    JongMan

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


    11년 전 link
  • User Avatar
    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]가 제대로 구해져있느냐? 하는 부분입니다. 알고리즘과 소스를 보고 잘못된 부분이 있으면 언제든 답변부탁드립니다.


    11년 전 link
  • User Avatar
    Kureyo

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


    11년 전 link
  • User Avatar
    Fate

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


    11년 전 link
  • User Avatar
    JongMan

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


    11년 전 link

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