글 읽기 - 1753번 구현 방법 질문입니다.

moonsoo5522 8년 전 0

제가 이 문제에 대한 간선 정보와 cost 관리를 연결리스트와 벡터를 이용해서 두가지로 해 봤습니다.

근데 연결 리스트로 자료구조를 구성했을땐 22% 수준에서 시간초과 나던게... 벡터 쓰니까 120ms 수준에서 끝나버리네요..

아무래도 연결리스트와 벡터의 시간차이가 그렇게 크지는 않을거같은데 ㅡ,ㅡ;; 제가 어떤 부분에서 구현을 잘못했나 싶어서 질문 드립니다.

아, 그리고 첫번째 노드는 헤드노드로 설정해서 사용하지 않았습니다. edge[i].next부터 실제 노드입니다.

struct NodeEdge
{
    int node; // 현재 노드와 이어진 이웃노드
    int cost; // 간선 비용
    struct NodeEdge *next;
};
struct NodeEdge edge[20001];
int main()
{
 
    int node, con, start;
    scanf("%d %d", &node, &con); // 노드 수, 노드간 간선의 수
    scanf("%d", &start);
    for (int i = 1; i <= node; i++)
        dist[i] = 987654321;
    dist[start] = 0;
    
    // 간선 및 cost정보 입력받기
    for (int i = 0; i < con; i++)
    {
        int temp;
        struct NodeEdge *pNext = NULL;
        scanf("%d", &temp);
        pNext = &edge[temp];
        while (pNext->next != NULL)
            pNext = pNext->next;
        struct NodeEdge *pTemp = new struct NodeEdge;
        scanf("%d %d", &(pTemp->node), &(pTemp->cost));
        pTemp->next = NULL;
        pNext->next = pTemp;
    }
    priority_queue<pair<int, int> >pq;
    pq.push(make_pair(0, start));
    while (!pq.empty())
    {
        int cost = -pq.top().first;
        int node = pq.top().second;
        pq.pop();
         
        if (cost > dist[node])
            continue;
        struct NodeEdge *pNext = edge[node].next;
        while (pNext != NULL)
        {
            int m_cost = cost + pNext->cost;
            int n_node = pNext->node;
 
            if (dist[n_node] > m_cost)
            {
                dist[n_node] = m_cost;
                pq.push(make_pair(-m_cost, n_node));
            }
            pNext = pNext->next;
        }
    }
}

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

문제

문제

출처

ICPC

1753번 구현 방법 질문입니다.

moonsoo5522 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말