17824번 - 아폴로니안 네트워크 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 | 512 MB | 15 | 5 | 5 | 83.333% |
문제
아폴로니안 네트워크는 무방향 그래프로, 삼각형에서 시작하여 중간에 있는 삼각형을 3개의 작은 삼각형으로 재귀적으로 분할하는 방식으로 구성된다.
가중치 있는 아폴로니안 네트워크에서, 가중치 합이 최대인 단순 경로의 가중치 합을 출력하라.
입력
첫 번째 줄에 정점의 개수 n이 주어진다. (3 ≤ n ≤ 250)
이후 3(n-2) 개의 줄에 간선의 정보 ai, bi, ci 가 주어진다. 해당 간선이 두 정점 ai, bi 를 ci의 가중치로 잇는다는 것이다. (1 ≤ ai, bi ≤ n, 0 ≤ ci ≤ 106)
주어진 그래프는 아폴로니안 네트워크이다.
출력
가중치 합이 최대인 단순 경로의 가중치 합을 출력하라.
예제 입력 1
3 1 2 1 2 3 1 3 1 2
예제 출력 1
3
예제 입력 2
10 1 2 4 2 3 4 3 1 3 6 1 3 6 2 3 6 3 4 4 6 4 4 3 4 4 2 3 5 1 3 5 6 3 5 2 4 10 1 4 10 3 3 10 6 3 7 1 4 7 10 4 7 6 3 8 1 3 8 3 4 8 10 4 9 3 4 9 8 3 9 10 3
예제 출력 2
35
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호