글 읽기 - 퇴근시간 문제 도와주세요....! long long int도 안되요...

QuqqU 6년 전 0

부동소수점 오차 때문에 틀릴 수도 있다 해서, 모든 정수에 2를 곱해서 사용했고요,

터질까봐 long long int 도 썼습니다.

그래도 1%에서 가차없이 나가는데 왜 그런가요?

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <functional>
#include <map>
#include <set>
#define INF 9999999
using namespace std;
typedef pair<long long int, long long int> ii;

vector<ii> edge[5005];
vector<long long int> dist(5005, INF);
priority_queue<ii, vector<ii>, greater<ii>> pq;

set<ii> st;
long long int s, e;

long long int whentraffic(long long int time, long long int dist, long long int from, long long int to) {
	if (st.count(ii(from, to))) {
		if (time < s) {//출근시간 이전에 시작
			long long int surdist = 0;
			if ((s - time) >= dist) // 출근시간 전에 종료
				return dist;
			else {//출근 시간이후에 종료
				surdist = dist - (s - time);
				if (surdist * 2 <= e - s) //종료시간 이전에 종료
					return dist * 2 - (s - time);//ok
				else //종료시간 이후에 종료
					return dist + (e - s) / 2;//ok//
			}

		}
		else if (s <= time && time < e) {//출근 시간 이후에 시작
			if (dist * 2 <= e - time)//종료시간 이전에 종료
				return dist * 2;//--ok
			else // 종료시간 이후에 종료
				return dist + (e - time) / 2;//ok
		}
		else//종료시간 이후에 시작
			return dist;//ok
	}
	return dist;//ok
}


int main() {
	long long int n, m; scanf("%lld %lld %lld %lld", &n, &m, &s, &e);
	s *= 2; e *= 2;
	for (long long int i = 0; i < m; i++) {
		long long int a, b, t1, t2; long long int l; scanf("%lld %lld %lld %lld %lld", &a, &b, &l, &t1, &t2);
		edge[a].push_back(ii(2 * l, b));
		edge[b].push_back(ii(2 * l, a));
		if (t1 == 1) st.insert(ii(a, b));
		if (t2 == 1) st.insert(ii(b, a));
	}

	dist[1] = 0;
	pq.push(ii(dist[1], 1));
	while (!pq.empty()) {
		long long int curr = pq.top().second;
		long long int currdist = pq.top().first;
		pq.pop();
		if (dist[curr] < currdist) continue;
		for (auto next : edge[curr]) {
			long long int ppp = whentraffic(dist[curr], next.first, curr, next.second);
			long long int nextdist = dist[curr] + ppp;
			if (dist[next.second] > nextdist) {
				dist[next.second] = nextdist;
				pq.push(ii(dist[next.second], next.second));
			}
		}
	}
	long long int ans = 0;
	for (long long int i = 1; i <= n; i++) {
		ans = max(ans, dist[i]);
		//printf("%d -> %d////", i, dist[i]);
	}
	printf("%lld", ans / 2);
	if (ans % 2 == 1) printf(".5");
	return 0;
}

chogahui05 6년 전 0

이 문제 어려운 거 같아요.

일단 문제 조건대로 해석해 보면, 혼잡한 길인 경우 퇴근 시간에 1초에 0.5씩 이동합니다.

그렇지 않은 경우 1초에 1씩 이동합니다.

이렇게 되어 있습니다.

그렇기 때문에, 어떤 경우에는 x.5초에 도로를 빠져 나올 수도 있다는 것이지요.

그러면 거꾸로 이렇게 생각해 봅시다.

0.5초 = 1 단위시간으로 생각해 봅시다.

속도도 정수 단위가 되어야 한다고 생각해 볼까요?

혼잡한 경우, 1단위시간에 1만큼 이동합니다.

안 혼잡한 경우 1단위시간에 2만큼 이동합니다.

그러면 혼잡한 경우에, 2단위시간에 2만큼, 안 혼잡한 경우 2단위시간에 4만큼 이동하네요.

원래 도로 길이에 4를 곱해야 한다는 느낌이 확 옵니다. 힌트는 여기까지 드리겠습니다.

chogahui05 6년 전 0

예를 하나 들어드리겠습니다.

원래 도로의 길이가 13이였습니다. 혼잡한 경우, 26초가 걸립니다.

이를 제가 말한 단위시간으로 환산하면 52단위시간이 걸리는군요.

혼잡한 경우, 1단위시간당 1만치 이동한다고 약속했으므로, 올바른 답이 나오기 위해서는 원래 도로 길이에 4를 곱해야 한다는 것을 알 수 있어요.

QuqqU 6년 전 0

속도 * 시간 = 거리 에서

시간이 double형으로 지정될 경우(0.5단위) 부동소수점 오차가 발생해 틀릴 수도있다고 하여,

속도 * (시간*2) = (거리*2) 로 시간과 거리만 2씩 곱해주어서 풀은 건데,

속도 까지 굳이 2를곱해 정수단위로 만들어야하는 이유는 무엇인가요??

whentraffic에서 모든 단위는 짝수로 돌아가서, 굳이 속도까지 2를 곱해줄 필요는 없지 않나요???(아닌가...??ㅠㅠ)

chogahui05 6년 전 0

퇴근 시간에 혼잡한 도로인 경우 1초에 0.5씩 가거든요.

QuqqU 6년 전 0

INF 가 너무 작아서 생기던거였습니다!

INF를 922222222222222222로 longlong int의 최댓값에 가깝게 바꾸니깐 되는군요!

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

문제

문제

출처

ICPC

퇴근시간 문제 도와주세요....! long long int도 안되요...

QuqqU 6년 전 0

chogahui05 6년 전 0

chogahui05 6년 전 0

QuqqU 6년 전 0

chogahui05 6년 전 0

QuqqU 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말