[BOJ/Gold 1] 백준 11781 퇴근 시간(C++)

문제 링크

https://www.acmicpc.net/problem/11781

11781번: 퇴근 시간

 

문제

엔지니어의 행복도는 퇴근 후 집에 도착하는 시각이 늦을수록 낮아진다는 것이 증명되었다.

조이의 대표 레드는 엔지니어의 행복도를 최대한 높여야 할 의무가 있기 때문에, 신중하게 퇴근 시간을 조정하기로 하였다.

하지만 퇴근 시간을 조정하려면 먼저 엔지니어들이 집에 도착하는 시간을 알아야만 했다.

이 문제를 미카에게 맡기려고 했지만, 6시가 넘어 미카는 이미 퇴근해버렸기 때문에 레드는 고민에 빠지고 말았다.

레드를 도와 레드와 조이 엔지니어 모두의 행복도를 높여보도록 하자!

회사가 있는 서울은 N개의 지점으로 되어있다.

각 지점은 1번부터 N번의 번호를 가지고 있고, 회사는 1번 지점에 있다.

M개의 도로들은 서로 다른 지점을 연결하고 있으며, 임의의 지점에서 모든 지점으로 이동할 수 있다.

각각의 도로는 길이를 가지고 있으며, 거리 1을 이동하는 데 1분이 걸린다.

편의상 퇴근은 0분에 한다고 가정한다.

서울은 퇴근 시간에 도로가 막힌다.

퇴근 시간이 아닐 때에는 거리 1을 이동하는 데 1분이 걸리지만,

퇴근 시간이 겹칠 경우 혼잡한 도로는 거리 1을 이동하는 데 2분이 걸리게 된다. (물론 퇴근 시간에 막히지 않는 도로도 있다.)

만약 퇴근 시간이 10분부터 20분이고 어떤 도로에 진입한 순간이 15분이며, 도로의 길이는 10이라면 이 도로를 전부 통과하는 데 걸리는 시간은

• 퇴근 시간 : 5분(15 ~ 20분)동안 간 거리 = 2.5를 가는 데 걸린 시간 : 5분
• 퇴근 시간 외의 시간 : 나머지 거리 7.5를 가는 데 걸린 시간 : 7.5분

총 12.5분이 된다.

입력

첫째 줄에는 N, M과 퇴근 시간의 시작과 끝을 의미하는 S와 E가 정수로 주어진다. (2 ≤ N ≤ 5,000, 1 ≤ M ≤ 100,000, 0 ≤ S < E ≤ 1,000,000,000)

다음 M개의 줄에는 서로 다른 정수 A, B와 도로의 길이를 의미하는 L, 그리고 t1, t2가 주어진다. (1 ≤ A, B ≤ N, 1 ≤ L ≤ 1,000,000,000, t1, t2 = 0 또는 1)

t1, t2는 A,B 사이에 퇴근 시간에 도로가 정체되는지 여부이다.

• t1 = 1 일 때는 퇴근 시간에 A에서 B로 이동시 정체됨을 의미하며,
• t2 = 1 일 때는 퇴근 시간에 B에서 A로 이동시 정체됨을 의미한다.
• 만약 t1 혹은 t2가 0이라면 각각의 이동시 정체되지 않음을 의미한다.

퇴근할 때는 같은 길로는 2번 이상 이동하지 않는다. 사원들은 언제나 최대한 빨리 집에 가고 싶어하기 때문에 일부러 늦는 길을 선택하지 않는다. 또한 이동할 때 멈추지 않고 계속 이동한다.

출력

모든 지점에 대해서 회사에서 출발했을 때 가장 늦게 도착하게 되는 지점까지의 도착 시각을 첫째 줄에 출력하라.

예제 입력 1

7 6 5 13
1 2 8 1 0
3 2 4 0 1
1 5 5 0 0
1 4 10 0 0
1 6 10 0 0
6 7 5 0 0

예제 출력 1

16

예제 입력 2

7 6 4 13
1 2 8 1 0
3 2 4 0 1
1 5 5 0 0
1 4 10 0 0
1 6 10 0 0
6 7 5 0 0

예제 출력 2

16.5

힌트

퇴근 시간이 없다면 7번에 도착하는 시각인 15분이 가장 늦게 된다.

하지만 3번까지 가는 경로가 정체가 되기 때문에 3번에 도착하는 시각이 16분으로 가장 늦게 된다.

• 1번 도로 : 5만큼 5분간 이동 -> 퇴근 시간 시작 -> 나머지 3을 6분동안 이동 : 11분만에 이동
• 2번 도로 : 2분동안 1만큼 이동 -> 퇴근 시간이 끝남 -> 나머지 3을 3분동안 이동 : 5분

합 16분

• 조이는 ICPC 문제 풀이 능력을 중요하다고 생각하고 있습니다.
• 이 문제를 푼 분에게는 조이코퍼레이션 지원 시 선착순 10명에게 서류전형 통과의 기회를 드리고 있습니다.
• 이외에도 BOJ문제를 많이 푸신 분은 지원 시 어드밴티지가 있습니다.
• 자세한 채용 정보는 http://zoyi.co/job 에서 확인해주세요.

알고리즘 분류

• 최단 거리 알고리즘

풀이

이게 왜 골드1밖에 안되는 지 모르겠다. 플래티넘 같은데

다익스트라를 1번 수행하는 평범한 다익스트라 문제 같아 보이지만 본인은 퇴근 시간을 따져서 최단 거리를 기록하는 것이 매우 힘들었다. 너무 안돼서 찾아보니, double형을 사용할 때 미세하게 발생하는 오차 때문에 틀렸다고 나오는 듯...

따라서 도로의 길이를 2배로 늘려서 정수(long long)형으로 최단 거리를 기록하고, 최종적으로 답을 구할 때 일단 답을 2로 나누고 답이 홀수면 .5를 붙여서 출력하도록 하였다.

이 문제가 많이 어려웠던 것이 바로 퇴근 시간을 따져서 최단 거리를 기록하는 부분이다.

1. 특정 지점에서 출발하는 시간이 퇴근 시간 전이다.

  I. 해당 도로의 길이를 다 걸어도 퇴근 시간 전이라면 도로의 길이가 곧 이동한 시간이 된다.

  II. 해당 도로의 길이를 걷는 도중에 퇴근 시간이 넘어간다.

    i. 퇴근 시간이 끝나기 전에 해당 도로의 길이를 다 걸었다면, (퇴근 시작 시간 - 출발 시간) + (남은 거리 * 2)가 이동한 시간이 된다.

    ii. 퇴근 시간이 끝나고도 도로를 걷는다면, (퇴근 시작 시간 - 출발 시간) + (퇴근 종료 시간 - 퇴근 시작 시간) * 2 + (남은 거리)가 이동한 시간이 된다.

2. 특정 지점에서 출발하는 시간이 퇴근 시간대다.

  I. 해당 도로의 길이를 다 걸어도 퇴근 시간 전이라면 도로의 길이 * 2가 곧 이동한 시간이 된다.

  II. 퇴근이 끝나도 도로를 다 못 걸었다면 (퇴근 종료 시간 - 출발 시간) * 2 + (남은 거리)가 이동한 시간이 된다.

3. 특정 지점에서 출발하는 시간이 퇴근 시간 이후라면 도로의 길이가 곧 이동한 시간이 된다.

코드

#include <iostream>
#include <string>
#include <cmath>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#include <climits>
#define FASTIO cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define MAX 5001
#define LL long long
#define INF 1e18

using namespace std;
struct INFO {
	LL Dest, Dist;
	bool T;
};

struct COMP {
	bool operator()(INFO A, INFO B) {
		return (A.Dist > B.Dist);
	}
};

LL N, M, S, E;
vector<INFO> Edge[MAX];
LL Cost[MAX];
LL answer = 0;

void Input() {
	cin >> N >> M >> S >> E;
	for (int i = 1; i <= N; i++) {
		Cost[i] = INF;
	}
	for (LL i = 0; i < M; i++) {
		LL A, B, L;
		bool T1, T2;
		cin >> A >> B >> L >> T1 >> T2;
		Edge[A].push_back({ B,L * 2,T1 });
		Edge[B].push_back({ A,L * 2,T2 });
	}
	S *= 2;
	E *= 2;
}

LL Calc(LL A, LL L) {
	if (A < S) { // A가 퇴근 시간 전일 때
		if (S - A >= L) { // 이동해야 하는 거리 L을 퇴근 시작 전까지 이동할 수 있다면
			return L;
		}
		else { // 퇴근 시작 시간을 오버해야 한다면
			LL L1 = S - A; // 시작 시간부터 퇴근 시작 시간까지 이동한 거리
			LL L2 = L - L1; // 퇴근 시작 시간부터 이동해야 할 남은 거리
			LL T1 = E - S; // 퇴근 시간
			if ((L2 * 2) <= T1) { // 이동해야 할 남은 시간이 퇴근 시간 동안 이동할 시간 이하라면
				return (L1 + (L2 * 2));
			}
			else { // L2가 L3을 초과한다면 L3만큼 이동하고 L4만큼 이동
				return (L + (T1 / 2));
			}
		}
	}
	else if ((A >= S) && (A < E)) { // A가 퇴근 시간 안에 있을 때
		LL T1 = E - A; // 출발할 때부터 퇴근까지의 시간
		if (T1 >= (L * 2)) { // 퇴근 끝나기 전까지 충분히 이동 가능하면
			return L * 2;
		}
		else { // 퇴근이 끝나도 더 가야 한다면
			return (L + (T1 / 2));
		}
	}
	else if (A > E) { // A가 퇴근 시간 이후일 때에는 분당 1을 이동할 수 있다.
		return L;
	}
}

void Dijkstra() {
	priority_queue<pair<LL, LL> > PQ;
	Cost[1] = 0;
	PQ.push(make_pair(0, 1));

	while (!PQ.empty()) {
		LL CurC = -PQ.top().first;
		LL CurX = PQ.top().second;
		PQ.pop();

		if (Cost[CurX] < CurC) {
			continue;
		}

		for (int i = 0; i < Edge[CurX].size(); i++) {
			LL nextC = Edge[CurX][i].Dist;
			LL nextX = Edge[CurX][i].Dest;
			bool isJam = Edge[CurX][i].T;
			if (isJam) { // 도로가 혼잡할 때
				LL newC = Calc(CurC, nextC);
				nextC = newC;
			}
			if (Cost[nextX] > CurC + nextC) {
				Cost[nextX] = CurC + nextC;
				PQ.push(make_pair(-Cost[nextX], nextX));
			}
		}
	};
}

void Find_Answer() {
	for (int i = 2; i <= N; i++) {
		answer = max(answer, Cost[i]);
	}
	if (answer % 2 == 0) {
		cout << answer / 2 << "\n";
	}
	else {
		cout << answer / 2 << ".5\n";
	}
}

int main() {
	FASTIO
	Input();
	Dijkstra();
	Find_Answer();

	return 0;
}