글 읽기 - acm craft 1005

prnuimeer 6년 전 0

자꾸 시간 초과가 나옵니다 어떻게 단축해야 할까요? 코드좀 자세히 읽어 봐주 세요

#include <stdio.h>
int route( int, int, int*, int(*)[ 2 ] );
int main()
{
    int T, N, K, W, i, j; 
    int R;
    scanf( "%d", &T );
    for( i = 1; i <= T; i++ ) {
        scanf( "%d%d", &N, &K ); 
        int Name[ 1000 ] = { 0 };
        for( j = 0; j < N; j++ ) {
            scanf( "%lf", &Name[ j ] );
        }
        int Next[ 100000 ][ 2 ] = { 0 };
        for( j = 0; j < K; j++ ) {
            scanf( "%d%d", &Next[ j ][0], &Next[ j ][1] );
        } 
        scanf( "%d", &W );
        R = route( W, K, Name, Next );
        printf( "%lf\n", R );
    }
    return 0;
}
int route( int W, int K, int* Name, int( *Next )[ 2 ] )
{    
    int i, j = 0;
    int max = 0;
    int Connect[ 1000 ] = { 0 };
    static int Memo[ 1000 ] = { 0 };
    if( Memo[ W - 1 ] != 0) {
        return Memo[ W - 1 ];
    }
    else {
        for( i = 0; i < K; i++ ) {
            if( Next[ i ][ 1 ] == W ) {
                Connect[ j ] = Name[ W - 1 ] + route( Next[ i ][ 0 ], K, Name, Next );
                if( max <= Connect[ j ] ) {
                    max = Connect[ j ];
                }
                j++;
            }
        }
        if( j != 0 ) {
            return max;
        }
        else {
            Memo[ W - 1 ] = Name[ W - 1 ];
            return Memo[ W - 1 ];
        }
    }
}

jwg8679 6년 전 0

DP로 시간초과납니다. 위상정렬 쓰셔야해요.

QuqqU 6년 전 0

다익스트라로 푸셔도됩니다

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

문제

문제

출처

ICPC

acm craft 1005

prnuimeer 6년 전 0

jwg8679 6년 전 0

QuqqU 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말