1. 문제 요약
[약속 장소 정하기]
1. 출발 위치는 약속 장소가 아니다.
2. 지헌이의 최단 시간 + 성하의 최단 시간이 최소가 되는 위치
3. 지헌이의 시간 <= 성하의 시간
4. 약속 장소가 여러곳이라면, 지헌이와 가장 가까운 곳이 최종 장소가 됨.
-> 만약 지헌이와의 거리도 같다면 번호가 가장 작은 순이 최종 장소가 됨.
해당 조건들은 1->2->3->4 순으로 만족해야 하는 것이 관건!!
2. 입출력
[입력]
1. 약속 장소 후보군 V(2<=V<=100), 장소를 연결하는 길이 수 M (1<=M<=1000)
3. 다음 M개의 줄에 a b c 주어짐
- a : 길의 시작, b : 길의 끝, c : 길을 건너는 시간 (c는 10000이하의 자연수)
- 길은 양방향이다.
4. 지헌이의 위치 J, 성하의 위치 S
[출력]
- 조건 충족되는 약속 장소의 위치
- 만날 순 있어도 조건이 충족되지 않으면 -1 출력
3. 조건
- 성하와 지헌이가 만날 수 있는 경우만 주어진다.
4. 알고리즘
- 지헌이와 성하의 dijkstra 알고리즘을 각각 수행해 배열을 생성한다.
- 다음과 같은 조건을 가지는 priorityQueue에 지헌과 성하의 다익스트라 배열의 합을 넣는다.
-> 두 배열의 합이 최소가 되어야 한다.
-> 합이 같다면, 지헌과 가까워야 한다.
-> 지헌과 가까운 거리가 같다면, 번호가 작아야 한다.
제가 정리한 내용 및 알고리즘 입니다. 대체 왜 틀린건지..ㅠㅠㅠ 설명해주실 고수분 계신가요..
jmj45 1년 전
1. 문제 요약 [약속 장소 정하기] 1. 출발 위치는 약속 장소가 아니다. 2. 지헌이의 최단 시간 + 성하의 최단 시간이 최소가 되는 위치 3. 지헌이의 시간 <= 성하의 시간 4. 약속 장소가 여러곳이라면, 지헌이와 가장 가까운 곳이 최종 장소가 됨. -> 만약 지헌이와의 거리도 같다면 번호가 가장 작은 순이 최종 장소가 됨. 해당 조건들은 1->2->3->4 순으로 만족해야 하는 것이 관건!! 2. 입출력 [입력] 1. 약속 장소 후보군 V(2<=V<=100), 장소를 연결하는 길이 수 M (1<=M<=1000) 3. 다음 M개의 줄에 a b c 주어짐 - a : 길의 시작, b : 길의 끝, c : 길을 건너는 시간 (c는 10000이하의 자연수) - 길은 양방향이다. 4. 지헌이의 위치 J, 성하의 위치 S [출력] - 조건 충족되는 약속 장소의 위치 - 만날 순 있어도 조건이 충족되지 않으면 -1 출력 3. 조건 - 성하와 지헌이가 만날 수 있는 경우만 주어진다. 4. 알고리즘 - 지헌이와 성하의 dijkstra 알고리즘을 각각 수행해 배열을 생성한다. - 다음과 같은 조건을 가지는 priorityQueue에 지헌과 성하의 다익스트라 배열의 합을 넣는다. -> 두 배열의 합이 최소가 되어야 한다. -> 합이 같다면, 지헌과 가까워야 한다. -> 지헌과 가까운 거리가 같다면, 번호가 작아야 한다. 제가 정리한 내용 및 알고리즘 입니다. 대체 왜 틀린건지..ㅠㅠㅠ 설명해주실 고수분 계신가요..