글 읽기 - 다익스트라 시간초과 문제

yeop9657 7년 전 1

안녕하세요.

해당 문제를 다익스트라로 풀었는데 계속해서 시간초과가 나옵니다. ㅠㅠ

어디서 시간을 줄여야 하는지 잘 모르겠습니다.

구동을 해보면 작은 값 만을 찾아가서 답은 나오는데 시간초과가 ㅠㅠ

이 방식으로 해야하는게 아닌가요?

#include <queue>
#include <cstdio>
using namespace std;

#define SIZE 201
#define INF 9999999L

int mDes[SIZE][SIZE];
int mArray[SIZE][SIZE];
bool mVisit[SIZE][SIZE];

int mMinDij(const int mMatrix);

int main(void)
{
    for (int mCount = 0; true; mCount++)
    {
        int mMatrix = 0;
        scanf("%d", &mMatrix);
        
        if (mMatrix == 0) { break; }
 
        for (int ii = 0; ii < mMatrix; ii++)
        {
            for (int jj = 0; jj < mMatrix; jj++)
            {
                scanf("%d", &mArray[ii][jj]);
                mDes[ii][jj] = INF; mVisit[ii][jj] = false;
            }
        }
        
        printf("problem %d: %d", mCount, mMinDij(mMatrix));
    }
    
    return 0;
}

int mMinDij(const int mMatrix)
{
    /* Integer */
    int mSubX = 0, mSubY = 0;
    
    /* Queue */
    queue<pair<int, int> > mPathQue;
    mPathQue.push(make_pair(mSubX, mSubY));
    
    /* Init */
    mDes[mSubX][mSubY] = mArray[mSubX][mSubY];
    mVisit[mSubX][mSubY] = true;
    
    pair<int, int> mTempPath;
    pair<int, int> mPath[] = {make_pair(1, 0), make_pair(0, 1), make_pair(-1, 0), make_pair(0, -1)};
    while (!mPathQue.empty())
    {
        if (mVisit[mMatrix-1][mMatrix-1]) { break; }
        
        int mMin = INF;
        mSubX = mPathQue.front().first;
        mSubY = mPathQue.front().second; mPathQue.pop();
        
        for (int ii = 0; ii < 4; ii++)
        {
            int mLowX = mSubX + mPath[ii].first;
            int mLowY = mSubY + mPath[ii].second;
            
            if ( (mLowX < 0 || mLowY < 0) || (mLowX >= mMatrix || mLowY >= mMatrix) ) { continue; }
            if (mVisit[mLowX][mLowY] || mDes[mLowX][mLowY] <= mDes[mSubX][mSubY]) { continue; }
            
            const int mSum = mDes[mSubX][mSubY] + mArray[mLowX][mLowY];
            if (mMin > mSum)
            {
                mMin = mSum;
                mDes[mLowX][mLowY] = mSum;
                mVisit[mLowX][mLowY] = true;
                mTempPath = make_pair(mLowX, mLowY);
            }
        }
        
        mPathQue.push(mTempPath);
    }
    
    return mDes[mMatrix-1][mMatrix-1];
}

yeop9657 7년 전 0

ㅠㅠ 해결방법좀 부탁드려요.

답답해서 미칠것같아요.

sgchoi5 7년 전 0

문제 출처 대회의 자료 참고하시길.....

http://gooddaytocode.blogspot....

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

문제

문제

출처

ICPC

다익스트라 시간초과 문제

yeop9657 7년 전 1

yeop9657 7년 전 0

sgchoi5 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말