글 읽기 - 13303 도움 요청합니다.

operaghost 6년 전 0

시간 초과가 납니다 ㅜㅜ

타 온라인 저지에 제출해보니 시간초과(51점)가 나옵니다.

어떤 전략이 필요한지 코멘트 해주시면 감사하겠습니다. ^^

#include<bits/stdc++.h>
#define Sz 100001
using namespace std;
typedef pair<int, int> pii;
 
queue<pii> Q; // 현재의 y좌표 위치와 단계의 정보
queue<int> T; // 각 단계까지의 이동한 거리
vector<pii> V; // 최소이동거리들 넣어주는 공간
 
struct DD{
    int x, yl, yh;
}D[Sz];
 
bool cmp(const DD &p, const DD &q){
    return p.x < q.x;
}
 
int N, Gx, Gy;
bool Chk[Sz];
 
int main(){
 
    scanf("%d %d %d", &N, &Gx, &Gy);
 
    Q.push(pii(-1, Gx)), T.push(0);
 
    for(int i = 0; i < N; i++){
        scanf("%d %d %d", &D[i].x, &D[i].yl, &D[i].yh);
    }
 
    sort(D, D + N, cmp);
 
 
    while(!Q.empty()){ // BFS + 그리디(더 짧은 거리 선택)
        int here = Q.front().second;
        int level = Q.front().first;
        int t = T.front();
        Q.pop(), T.pop();
 
        if(level == N - 1){ // 마지막 단계일 때
            V.push_back(pii(t, here));
            continue;
        }
 
        if(D[level+1].yl < here && here < D[level+1].yh){ 
            Q.push(pii(level + 1, D[level + 1].yl));
            T.push(t + abs(here - D[level + 1].yl));
            Q.push(pii(level + 1, D[level + 1].yh));
            T.push(t + abs(here - D[level + 1].yh));
        }
        else{
            Q.push(pii(level + 1, here));
            T.push(t);
        }
    }
 
    sort(V.begin(), V.end());
 
    printf("%d\n", V[0].first + Gy);
 
    Chk[0] = 1;
    int cnt = 1, ed;
    for(int i = 1; i < V.size(); i++){
        if(V[0].first == V[i].first &&  V[i].second != V[i-1].second) cnt++, Chk[i] = true;
        if(V[0].first != V[i].first){
            ed = i;
            break;
        }
    }
 
    printf("%d ", cnt);
 
    int cnt1 = 0;
    for(int i = 0; ; i++){
        if(Chk[i]){
           printf("%d ", V[i].second);
           if(++cnt1 == cnt)break;
        }
    }
 
return 0;
}

sgchoi5 6년 전 0

얘는 정답이랑 설명이 있으니 한 번 참고 하시면 좋을 듯 하네요.

http://gooddaytocode.blogspot....

operaghost 6년 전 0

모범 소스가 존재하긴 하나

가독성이 떨어져서 잘 모르겠어요..

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

문제

문제

출처

ICPC

13303 도움 요청합니다.

operaghost 6년 전 0

sgchoi5 6년 전 0

operaghost 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말