글 읽기 - (도움) 70%대에서 시간초과 나시는 분들 참고(특히 73%)

limequeen 2년 전 1

70%대에서 시간초과 나시는 분들(특히 73%)

[서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의한다.] 조건 무시하시고 풀어보세요.

저는 이 조건을 너무 신경 쓴 나머지 간선이 존재하는지, 존재한다면 w보다 작은지 확인하고 수정(추가)하는 방식으로 했었는데요.

이게 생각보다 시간이 많이 걸리는 것 같더라고요.

그래서 이를 무시하고 여러 개의 간선이 들어오든 말든 체크하지 않고 무조건 넣어주니 시간초과가 더 이상 뜨지 않더라고요!

문제 해결에 도움이 되셨으면 좋겠습니다! :D

(코드는 이해를 위해 간선을 확인 하는 경우와 확인하지 않는 경우만 넣었습니다)

// 간선이 존재하는지 일일이 확인 하는 경우 (시간초과)
int u, v, w;
int flag = 0;
vector<pair<int,int>>::iterator iter;
for(int i=0; i<edge_count; i++)
{
    cin >> u >> v >> w;

    flag = 0;
    for(iter=adj_list[u].begin(); iter!=adj_list[u].end(); iter++)
    {
        if(iter->first == v)
        {
            flag == 1;
            if(iter->second > w)
            {
                iter->second = w;
                break;
            }
        }
    }
    if(!flag)
        adj_list[u].push_back(make_pair(v, w));
}

// 중복간선을 체크하지 않고 넣는 경우 (맞았습니다!)
int u, v, w;
for(int i=0; i<edge_count; i++)
{
    cin >> u >> v >> w;

    adj_list[u].push_back(make_pair(v, w));
}

osm0822 1년 전 0

만약 중복간선을 체크해야 한다면 HashSet을 이용하면 상수시간에 해결 가능할것 같습니다.

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

문제

문제

출처

ICPC

(도움) 70%대에서 시간초과 나시는 분들 참고(특히 73%)

limequeen 2년 전 1

osm0822 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말