글 읽기 - 퇴근시간대 case 에 대해서 질문있습니다.

nisroeld99 7년 전 0

20프로 부근에서 계속 틀렸다고 뜹니다 ㅠㅠ

자료형 관련 대충 포멧은 다 맞는거같은데 틀리네요 .

정체구간에서 가능한 case 들을 구분해서 작성했습니다.

case 1. 현재까지 걸린 시간 (= cost ) < s --> 간선에 진입하기 전부터 퇴근시간..

case 1-1 :

case 1-2 :

case 2. 현재까지 걸린 시간(=cost ) > s --> 간선에 진입하고 나서 도중에 퇴근시간이 시작됨.

case 2-1 :

case 2-2 :

case 3. --> 정체구간이지만, 퇴근시간과 겹치지 않음 .. (평범한 간선과 동일하게 pq 추가)

이런식으로 작성했는데

100% 혼자 어렵게 생각하는거 같네요

방법 힌트 좀 주시면 감사하겠습니다.

어떻게 할까요 될듯말듯하면서 안됩니다ㅁㅇㅎ라ㅐㅓㅇㅁㄹ하ㅐㅓㄴㅁㅇ

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <queue>
#include <vector>
using namespace std;
typedef long long ll ;
typedef pair<double, int> di;
typedef  pair<int,int > ii;
typedef pair<ll ,ii> iii;
int n , m;
ll s,e;
vector<iii> g[5555];
bool c[5555];
double d[5555];
priority_queue< di,vector<di> , greater<di> > pq ;
void dijk(int start){
     
    for (int i = 1 ; i<=n;i++){
        d[i]=198765432100000000000000000000000.0;
        c[i]= false;
    }
    d[start]= 0.0;
    pq.push(ii( 0.0 , start) );
    while (!pq.empty()){
        ii temp = pq.top(); pq.pop();
        double cost = temp .first;
        ll now = temp. second;
         
        if (c[now])continue;
        c[now] =true ;
         
        for (int i = 0 ; i< g[now].size(); i++){
            double len = (double)g[now][i].first;
            double next_cost = len + cost ;
             
            int next = g[now][i] .second.first;
            int next_tg = g[now][i].second.second;
             
            if (  next_tg && !( e<= cost ) && ! (s >= next_cost) ){ // 퇴근시간이면
                if ( s < cost){//간선 진입할때부터 계속 퇴근시간대였음
                     
                    double time = len*2 +cost;
                    if ( time >= e  ){// 간선이 끝나기전에 퇴근시간이 끝날때,
                        double gan_len = ((double)e-cost)/2 ;
                        double temp  = ((len - gan_len) + (double)e-cost) +cost;
                        if (d[next] > temp){
                            d[next]= temp;
                            pq.push(ii(temp,next));
                        }
                    }else {     //끝까지 간다고 가정했을떄,
                        if (d[next] > time){
                            d[next]= time;
                            pq.push(ii( time , next ));
                        }
                         
                    }
                }else if (s>= cost) { // 간선에 진입한 후, 퇴근 시간이 된 경우
                    double gan_len = ((double)s-cost);
                     
                    double temp = (len - gan_len)*2 +gan_len;
                     
                     
                    if ( temp>= e ){ //간선 끝나기전에 끝날때
                        double nx_cost =  cost + gan_len + ((double)e-s) + (len - gan_len - (e-s)/2);
                        if (d[next]> nx_cost){
                            d[next]= nx_cost;
                            pq.push({nx_cost,next});
                        }
                    }else {   //끝나도 끝나지 않음
                        double nx_cost = cost + gan_len + (len - gan_len)*2;
                        if (d[next]> nx_cost){
                            d[next]= nx_cost;
                            pq.push({nx_cost,next});
                        }
                    }
                     
                }else {
                    if ( d[next] > next_cost){
                        d[next] = next_cost;
                        pq.push(ii( next_cost,next));
                    }
                }
                 
            }
             
            else {  // 정체 구간아니면 그냥 pq 에 추가하기
                if ( d[next] > next_cost){
                    d[next] = next_cost;
                    pq.push(ii( next_cost,next));
                }
            }
        }
    }
     
     
     
}
 
 
 
int main(){
    scanf("%d%d%lld%lld",&n,&m,&s,&e);
    while ( m -- ){
        int from, to;
        ll cost;
        int t1,t2;
        scanf("%d%d%lld%d%d",&from,&to,&cost ,&t1,&t2);
        g[from].push_back(iii(cost,ii(to,t1)));
        g[to].push_back(iii(cost,ii(from,t2)));
    }
     
    dijk(1);
    double dab = -1000000000;
    for (int i = 1; i<=n; i++){
        dab = max ( dab, d[i] );
    }
    cout.precision(numeric_limits<double>::digits10 + 1);
    cout<<dab;
}

simm4256 7년 전 0

42줄 '='넣으시고

45줄 '=''빼시고

59줄 '='빼시고

65줄 = 빼시고...

등등...

기본 범위설정이 잘못되어있네요.

가령 s=cost인 경우엔

출발할 때부터 퇴근시간인 경우이기 때문에

42줄의 if문에 들어가야 하는 케이스입니다.

퇴근시간 범위에 대해 다시한번 생각해보세요.

nisroeld99 7년 전 0

해봤는데 여전히 안되네요 일단 패스하겠습니다 ㅠㅠ

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

문제

문제

출처

ICPC

퇴근시간대 case 에 대해서 질문있습니다.

nisroeld99 7년 전 0

simm4256 7년 전 0

nisroeld99 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말