에너지 관리 로봇
골드 III의견: 0
미래 도시 물류 로봇은 \(N\)개의 거점 사이를 이동한다. 로봇은 거점 \(S\)에서 출발하여 거점 \(T\)에 도달해야 한다.
로봇의 최대 연료 용량은 \(F\)이고, 출발 시 연료는 \(F\)로 가득 차 있다. 각 도로 \(u \to v\)는 연료 소비량 \(w\)와 이동 비용 \(c\)가 있으며, 현재 연료가 \(w\) 이상일 때만 이 도로를 이용할 수 있다. 도로를 이용하면 연료는 \(w\)만큼 줄어들고 비용은 \(c\)만큼 늘어난다.
일부 거점에는 주유소가 있다. 로봇이 주유소에 도착하면 즉시 연료가 \(F\)로 회복된다.
거점 \(T\)에 도달하는 최소 총 비용을 구하여라. 불가능하면 \(-1\)을 출력한다.
- \(2 \le N \le 1\,000\)
- \(0 \le M \le 10\,000\)
- \(1 \le S, T \le N\), \(S \ne T\)
- \(1 \le F \le 200\)
- \(0 \le K \le N\)
- \(1 \le u, v \le N\), \(u \ne v\)
- \(1 \le w \le F\) (연료 소비량은 최대 연료 이하)
- \(1 \le c \le 10^6\)
첫째 줄에 거점의 수 \(N\), 도로의 수 \(M\), 출발 거점 \(S\), 도착 거점 \(T\), 최대 연료 용량 \(F\)가 공백으로 구분되어 주어진다.
둘째 줄에 주유소의 수 \(K\)가 주어진다.
셋째 줄에 주유소가 있는 거점 번호 \(K\)개가 공백으로 구분되어 주어진다. \(K = 0\)이면 셋째 줄은 빈 줄이다.
다음 \(M\)개의 줄에 도로 정보 \(u\ v\ w\ c\)가 주어진다. 거점 \(u\)에서 거점 \(v\)로 연료 \(w\)를 소비하고 비용 \(c\)로 이동할 수 있다.
거점 \(T\)에 도달하는 최소 총 비용을 출력한다. 불가능하면 \(-1\)을 출력한다.
5 5 1 5 5
1
3
1 2 3 10
2 3 3 5
3 5 3 8
1 4 2 1
4 5 6 20
-1
연료 용량은 \(5\)입니다. \(1\to4\to5\): 연료 소비 \(2+6=8 > 5\)이므로 불가능. \(1\to2\to3\): 연료 \(3+3=6 > 5\)이므로 직접 이동 불가. 하지만 \(1\to2\): 연료 \(3\) 소비(\(5\to2\) 남음), \(2\to3\): 연료 \(3\) 소비 — 불가(남은 연료 \(2 < 3\)). 따라서 \(1\to4\) (연료 \(5\to3\)), \(4\)에서 \(5\)로는 연료 \(6\) 필요 — 불가. 경로 \(1\to2\) (연료 \(5\to2\)), 이후 \(2\to3\) 불가. 가능한 경로: \(1\to4\) (연료 \(2\) 소비, 비용 \(1\), 남은 \(3\)), 더 이상 \(4\)에서 \(5\)로는 연료 \(6\) 필요 — 불가. 결국 가능한 경로: \(1\to2\) (연료 \(5\to2\), 비용 \(10\)), \(2\to3\) 불가. 유일한 방법은 없어 \(-1\)을 출력합니다. 실제로 연료 \(5\)로는 \(3\)번 주유소에 도달할 수 없습니다.
4 4 1 4 3
1
2
1 2 2 5
2 3 2 3
3 4 2 7
1 3 5 100
-1
연료 용량 \(3\). 공항(주유소)은 \(2\)번 거점. \(1\to2\): 연료 \(2\) 소비(남은 \(1\)), 비용 \(5\). \(2\)에서 주유 — 연료 \(3\)으로 회복. \(2\to3\): 연료 \(2\) 소비(남은 \(1\)), 비용 \(3\). \(3\to4\): 연료 \(2\) 소비(남은 \(-1 < 0\)) — 불가. 대신 \(3\)에서 주유가 없으므로 \(3\to4\)는 연료 \(2\)가 필요한데 남은 게 \(1\). 경로 \(1\to2\to3\to4\)는 \(3\)에서 막힘. \(1\to3\) 직접: 연료 \(5 > 3\) — 불가. 따라서 \(-1\)을 출력합니다.
4 3 1 4 3
2
2 3
1 2 2 5
2 3 2 3
3 4 2 7
15
연료 용량 \(3\), 주유소: 거점 \(2\), \(3\). \(1\to2\) (연료 \(2\) 소비, 비용 \(5\), \(2\)에서 주유) \(\to\) \(2\to3\) (연료 \(2\) 소비, 비용 \(3\), \(3\)에서 주유) \(\to\) \(3\to4\) (연료 \(2\) 소비, 비용 \(7\)). 총 비용 \(15\).
riseoj 작성
출처 Original
평가 및 의견
에너지 관리 로봇
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
에너지 관리 로봇