rhkd2612   4년 전

long형으로 바꿔도 안되요

ehddml3   4년 전

5가 나와야하지 않을까요

4 6
1 2 3
2 3 3
3 4 1
1 3 5
2 4 5
1 4 4
1 3

rhkd2612   4년 전

ehddml3


그러면 그래프가

0 3 5 4 

3 0 3 5 

5 3 0 1

4 5 1 0 인데

1 - 3  - 4 = 5 + 1 = 6이고

그 반대 케이스는 안되지 않나요?

ehddml3   4년 전

아.. 제가 잘못봤네용..

대신 코드에서 틀린부분을 찾아왔어요

if (nDistance < cost[from][i])

                q.push(make_pair(nDistance, nDirect));

이 부분에서 cost[from][nDirect] 를 cost[from][i]로 쓰셨어요

rhkd2612   4년 전

감사합니다 바로통과했어요

ehddml3   4년 전

그리구 pq에서 뽑아낸 다음에 cost를 바꾸는건 pq 크기가 더 늘어기 쉬워서 시간이 좀 빡빡하면 시간초과가 날 수 있어요

cost[from][from]=0;
while (!q.empty())
{
    pair<int, int> p = q.top(); q.pop();

    if (cost[from][p.second] < p.first)
        continue;

    for (int i = 0; i < vec[p.second].size(); i++)
    {
        int nDirect = vec[p.second][i].first;
        int nDistance = p.first + vec[p.second][i].second;

        if (nDistance < cost[from][nDirect]){
            q.push(make_pair(nDistance, nDirect));
            cost[from][nDirect]=nDistance;
        }
    }
}

이런식으로 쓰면 더 빨리 돌아갑니다

rhkd2612   4년 전

조언 감사합니다

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