글 읽기 - 틀리는 이유가 무엇일까요 ㅠ ㅠ (Javascript)

hagtfms 3년 전 0

고수님들... 엉엉...

const input = require('fs').readFileSync('dev/stdin').toString().split('\n').map(x=>x.split(' ').map(x=>+x));
const [N, M, S, E] = [input[0][0], input[0][1], input[0][2]*2, input[0][3]*2];
const INF = 2**50;

const g = new Array(N+1).fill(0).map(_=>new Array(N+1));
for(let i=1; i<=M; i++){
    const [A,B,L,t1,t2] = input[i];
	g[A][B] = [L*2, t1];
	g[B][A] = [L*2, t2];
}

function getElapseTime(i, j, startTime){
    if(!g[i][j]) return INF;

    const [L, isStationary] = g[i][j];
	if(!isStationary){
        return L;
	}else{
        if(E <= startTime || startTime+L <= S){
            return L;
        }else{ // 중간에 무조건 혼잡한 경우
            if(startTime < S){
                const T = (S - startTime);
                const R = (E - S) * 0.5; // 혼잡시간 이동 거리
                if(L <= T + R){ // 거리 비교
                    return T + (L-T)*2;
                }else{
                    return T + R*2 + (L - (T+R));
                }
            }else{
                const R = (E - startTime) * 0.5;
                if(L <= R){
                    return L*2;
                }else{
                    return R*2 + (L - R);
                }
            }
		}
	}
}

const d = new Array(N+1).fill(INF);
for(let i=2; i<=N; i++){
    d[i] = getElapseTime(1, i, 0);
}
for(let i=2; i<=N; i++){    
    for(let j=2; j<=N; j++){
        if(i !== j){
            const time = d[j] + getElapseTime(j, i, d[j]);
            if(time < d[i]) d[i] = time;
        }
    }
}

const answer = d.filter(x => x !== INF).reduce((a,c)=>Math.max(a,c));
console.log(Math.floor(answer/2) + ((answer%2)? ".5": ""));

hagtfms 3년 전 0

다익스트라에서 경로가 가장 짧은 정점을 구하지 않아서 그런 걸까요

이거 예전에 분명히 반례를 찾았었는데 기억이... 안 나네요

...

hagtfms 3년 전 0

시작점에서 가장 짧은 거리를 구한 후,

INF가 2**20이면 1% 실패, 2**40이어도 중간에 실패하고 2**50이면 통과하네요

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

문제

문제

출처

ICPC

틀리는 이유가 무엇일까요 ㅠ ㅠ (Javascript)

hagtfms 3년 전 0

hagtfms 3년 전 0

hagtfms 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말