MOVE TLE 관련 질문입니다.

  • sven
    sven

    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]);
}

    11년 전
8개의 댓글이 있습니다.
  • JongMan
    JongMan

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


    11년 전 link
  • sven
    sven

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


    11년 전 link
  • sven
    sven

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


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

    11년 전 link
  • JongMan
    JongMan

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


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

    11년 전 link
  • sven
    sven

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


    11년 전 link
  • Being
    Being

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


    11년 전 link

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