운송 문제 도와주세요..

  • l10veu
    l10veu

    자꾸 런타임 에러가 나는데 왜 그런지 잘 모르겠네요;;

    http://www.algospot.com/problems/read/MOVE


    #include
    #include
    #include
    #include
    #include
    #include

    using namespace std;

    int main()
    {
    int c;
    scanf("%d", &c);

    const int MAX = 10000;

vector<pair<int, long long> >* arr = new vector<pair<int, long long> >[MAX];
long long* dist = new long long[MAX];
bool* contain = new bool[MAX];
priority_queue<pair<long long, int> > pq;
while(c-- > 0)
{
    int n, m;
    scanf("%d %d", &n, &m);

    for (int i=0; i<n; ++i)
        arr[i].clear();
    fill(dist, dist + n, INT_MAX);
    fill(contain, contain + n, false);

    for (int i=0; i<m; ++i)
    {
        int a, b;
        long long d;
        scanf("%d %d %lld", &a, &b, &d);
        arr[a].push_back(make_pair(b, d));
        arr[b].push_back(make_pair(a, d));
    }

    if (n <= 0)
    {
        printf("0\n");
        continue;
    }

    dist[0] = 0;
    while( ! pq.empty())
        pq.pop();
    pq.push(make_pair(0, 0));
    while ( ! pq.empty())
    {
        pair<long long, int> t = pq.top();
        pq.pop();
        if ( ! contain[t.second])
        {
            contain[t.second] = true;
            if (t.second == n-1)
                break;
            for (vector<pair<int, long long> >::iterator i=arr[t.second].begin(); i!=arr[t.second].end(); ++i)
            {
                if ( ! contain[(*i).first])
                {
                    long long ndist = dist[t.second] + (*i).second;
                    if (ndist < dist[(*i).first])
                    {
                        dist[(*i).first] = ndist;
                        pq.push(make_pair(-ndist, (*i).first));
                    }
                }
            }
        }
    }

    printf("%lld\n", dist[n-1]);
}

return 0;

    }


    14년 전
3개의 댓글이 있습니다.
  • Taeyoon_Lee
    Taeyoon_Lee

    제가 예전에 AC받았던 소스를 그대로 붙여 넣어도 WA가 나오네요. 뭔가 문제가 생긴 것 같은데, 어디가 문제인지 찾아보는 중입니다.


    14년 전 link
  • Taeyoon_Lee
    Taeyoon_Lee

    l10veu님의 소스에는 별 문제가 없는 것 같습니다. 아마 채점 시스템의 문제인 것 같네요. 다만 vector를 new 할당해서 쓰는 건, 난생 처음 보는 코드라 조금 당황스럽군요. 그리고 어차피 이러나 저러나 똑같은 거

    그냥 전역 변수로 쓰는 게 좋아 보입니다.

    const int MAX = 10000;
    vector＜＜pair＜int, long long> > arr[MAX];
    long long dist[MAX];
    bool contain[MAX];

    int main()
    {
    blahblah~
    }

    아니면 vector의 취지를 살려, 아래처럼 쓰는 것도 생각해볼 수 있겠지요.

    vector＜vector＜＜pair＜int, long long> > > arr = vector＜＜pair＜int, long long> > (MAX);


    14년 전 link
  • l10veu
    l10veu

    네 감사합니다~


    14년 전 link

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