2129번 - 드라이브 파이널 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 128 MB | 140 | 22 | 16 | 15.534% |
문제
N(1≤N≤100)개의 도시들로 이루어진 나라가 있다. 이들 중 몇 개의 도시들은 서로 도로로 연결되어 있다. 당신은 당신의 취미 생활인 자동차 드라이브를 즐기려고 한다. 각각의 도시는 0, 1, 2, …, N-1의 번호가 붙어 있고, 현재 당신은 S번 도시에 위치하고 있으며, 당신은 T번 도시로 이동하려 한다.
각각의 도로는 그 도로의 길이와, 그 도로를 이용할 때 생기는 피로도가 있다. 피로도 값은 때로는 음수일 수도 있는데, 이는 그 도로를 드라이브 할 때 만족감을 얻는 경우이다. 또한 같은 도시들을 연결하는 도로라 하더라도, 어느 방향으로 운전하느냐에 따라 마주치는 경치가 다르기 때문에 피로도 역시 달라질 수 있다.
당신은 가능하면 피로도 값의 총 합을 최소로 하는 경로로 이동하려 한다. 그런 경우가 여러 가지 있다면 길이의 총 합이 최소인 경로를 찾으려고 한다. 단, 당신은 이동을 할 때, 각각의 도시에 연결된 도로들 중 피로도가 최소인 도로만을 이용할 수 있다.
예를 들어 위와 같은 경우를 보자. 각 도로 위에 []로 둘러싸인 값이 그 도로의 길이이고, 좌우의 값은 각 방향으로 그 도로를 이용할 때의 피로도이다. 위의 예에서의 최적해는 0-2-4-3-5가 된다. 이때의 피로도 합은 2(=-1+3+0+0)이고, 길이는 50(5+10+5+30)이다. 0-1-4-3-5 역시 피로도 합이 2이지만, 이는 길이가 51이기 때문에 최적해는 아니다. 0-3-5와 같은 경로는 피로도 합이 0이지만, 각 도시에 연결된 도로들 중 피로도가 최소인 도로만 이용한다는 조건에 어긋나므로 답이 될 수 없다.
각 도로들에 대한 정보를 입력받아 최적해를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 네 정수 N, M(0≤M≤5,000), S, T가 주어진다. 다음 M개의 줄에는 각 도로에 대한 정보를 나타내는 다섯 정수 u, v, a, c, b 가 주어진다. 이는 u번 도시와 v번 도시를 연결하는 길이 c의 도로가 있고, u->v 방향으로는 피로도가 a, v->u 방향으로는 피로도가 b라는 의미이다. 길이는 1이상 100이하의 정수이고, 피로도는 -100이상 100이하의 정수이다. 두 도시 사이에 여러 개의 도로가 있을 수도 있다.
출력
첫째 줄에 피로도 총 합과 길이 총 합을 출력한다. 만약 최적해가 없다면 VOID를 출력한다. 만약 답이 무한히 작아질 수 있다면 UNBOUND를 출력한다.
예제 입력 1
7 11 0 5 0 1 -1 6 4 0 2 -1 5 4 0 3 0 1 0 1 4 3 10 1 2 4 3 10 1 3 4 0 5 0 3 5 0 30 0 3 5 1 20 0 4 6 0 3 1 6 5 1 8 0 6 6 0 2 -1
예제 출력 1
2 50
출처
ICPC > Regionals > Europe > Southeastern European Regional Contest > SEERC 2005 F번
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호