MOVE TLE 관련 질문입니다.

  • User Avatar
    sven

    [[problem:MOVE]]
    bellman - ford 알고리즘으로 짰습니다.
    계속 TLE가 떠서 최대한 줄여보았는데, 아직도 뜨네요 ㅜㅜ
    여기서 어떤 식의 개선이 가능할까요?

    아래는 코드입니다.

    #include <memory>
#include <cstdio>
#include <climits>

#define X INT_MAX

using namespace std;

void solve();

int main()
{
    int T;
    scanf("%d", &T);
    while(T--)
        solve();
}

void solve()
{
    int N, M;
    scanf("%d%d", &N, &M);
    long D[2][N];
    int A[M][3];
    for(int i=0; i<=1; i++)
        for(int j=0; j<N; j++)
            D[i%2][j] = X;
    for(int i=0; i<M; i++)
        scanf("%d%d%d", &A[i][0], &A[i][1], &A[i][2]);
    
    D[0][0] = 0;
    int j = -1;
    while(j++ < N)
    {  
        bool k = j%2;
        copy(D[k], D[k] + N, D[!k]);
        for(int i=0; i<M; i++)
        {
            D[!k][A[i][1]] = min(D[k][A[i][0]] + A[i][2], D[!k][A[i][1]]);
            D[!k][A[i][0]] = min(D[k][A[i][1]] + A[i][2], D[!k][A[i][0]]);
        }
    }
    printf("%d\n", D[N%2][N-1]);
}

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

    알고리즘을 바꾸셔야겠네요;; bellman-ford 알고리즘의 시간 복잡도는 O(VE)입니다. N=10000이고 M=20000이면 시간 안에 안나오는것이 당연하지요.


    14년 전 link
  • User Avatar
    sven

    헉 이 시간에 안주무시다니..
    다른 어떤 알고리즘이 있을까요? 음의 값을 가지는 도로가 있어서 다익스트라는 안되는 것 같아요.


    14년 전 link
  • User Avatar
    sven

    음 한가지 더 질문드릴게요.
    실행 시간은 어떻게 예측하시나요?
    (시간 복잡도 개념은 알고 있습니다.)
    time 명령어로 실험해보니, 108 기준으로, int 변수형의 더하기 곱하기 쓰기 비교하기는 0.3 ~ 0.4초가 걸리기에, 저는 108의 연산 시간을 상수 초 정도로 생각하고 있었습니다.


    14년 전 link
  • User Avatar
    Being
    1. '음의 값을 가지는 도로'가 있다는 이야기가 명시적으로 없고, 문제에서 '도시'와 '도로'를 사용해 서술했으면 상식 선에서 도로의 길이는 양수여야 하지 않을까요. 너무 그렇게 지나친 가정을 하지 않으셔도 됩니다.
      • 덧붙여, 음의 값을 가지는 도로가 있었다면 문제에서 기술해주어야 할 것이 훨씬 많아집니다. (음수 사이클의 존재 여부 등)
    2. 수행 시간은 대강 그 정도 규모로 생각하시면 되고, 해서 1억 회의 루프 이터레이션 정도면 1초로 가정하는 것이 일반적입니다. 이 문제의 경우 108의 연산 시간이 상수 초면 그런 케이스가 두세 개 정도만 입력에 들어와도 시간 안에 절대 처리하지 못하겠지요.

    14년 전 link
  • User Avatar
    JongMan

    오 빙군이 대답을 잘해줬네요. 근데 각 도로의 길이가 양수라는 것은 문제에 쓰여 있는 게 좋을 것 같습니다. 제보 감사드립니다. ^


    14년 전 link
  • User Avatar
    JongMan
    1. 입력에 주어지는 모든 수는 음이 아닌 정수라는 항목을 추가했습니다.
    2. 아 글고 제가 늦은 시간에 리플을 다는건 제가 지금 해외에 있어서 그렇습니다. ;

    14년 전 link
  • User Avatar
    sven

    아... 처음에 assert(길이 > 0)에 걸리기에 음의 값을 가지는 도로가 있다고 생각했었는데, aseert(길이 >= 0) 하니까 안걸리네요!
    질문 답변 감사드립니다.


    14년 전 link
  • User Avatar
    Being

    아.. 길이 == 0 인 경우도 솔직히 양심없는 것 같긴 한데 ㅋㅋ 뭐 문제에 썼으니 상관없겠지요.


    14년 전 link

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