Logo
(追記) (追記ここまで)

17824번 - 아폴로니안 네트워크 다국어

시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 512 MB2810753.846%

문제

아폴로니안 네트워크는 무방향 그래프로, 삼각형에서 시작하여 중간에 있는 삼각형을 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

힌트

W3sicHJvYmxlbV9pZCI6IjE3ODI0IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjNTQ0XHVkM2Y0XHViODVjXHViMmM4XHVjNTQ4IFx1YjEyNFx1ZDJiOFx1YzZjY1x1ZDA2YyIsImRlc2NyaXB0aW9uIjoiPHA+XHVjNTQ0XHVkM2Y0XHViODVjXHViMmM4XHVjNTQ4IFx1YjEyNFx1ZDJiOFx1YzZjY1x1ZDA2Y1x1YjI5NCBcdWJiMzRcdWJjMjlcdWQ1YTUgXHVhZGY4XHViNzk4XHVkNTA0XHViODVjLCBcdWMwYmNcdWFjMDFcdWQ2MTVcdWM1ZDBcdWMxMWMgXHVjMmRjXHVjNzkxXHVkNTU4XHVjNWVjIFx1YzkxMVx1YWMwNFx1YzVkMCBcdWM3ODhcdWIyOTQgXHVjMGJjXHVhYzAxXHVkNjE1XHVjNzQ0IDNcdWFjMWNcdWM3NTggXHVjNzkxXHVjNzQwIFx1YzBiY1x1YWMwMVx1ZDYxNVx1YzczY1x1Yjg1YyBcdWM3YWNcdWFkYzBcdWM4MDFcdWM3M2NcdWI4NWMgXHViZDg0XHVkNTYwXHVkNTU4XHViMjk0IFx1YmMyOVx1YzJkZFx1YzczY1x1Yjg1YyBcdWFkNmNcdWMxMzFcdWI0MWNcdWIyZTQuJm5ic3A7PFwvcD5cclxuXHJcbjxjZW50ZXI+PGltZyBhbHQ9XCJcIiBzcmM9XCJodHRwczpcL1wvdXBsb2FkLmFjbWljcGMubmV0XC8zMGE5NmVjYS04ZTg1LTRmOTgtODdhMi05OTY2ZTM1OWYzMThcLy1cL3ByZXZpZXdcL1wiIHN0eWxlPVwid2lkdGg6IDIwMHB4OyBoZWlnaHQ6IDE3M3B4O1wiIFwvPjxcL2NlbnRlcj5cclxuXHJcbjxwPlx1YWMwMFx1YzkxMVx1Y2U1OCBcdWM3ODhcdWIyOTQgXHVjNTQ0XHVkM2Y0XHViODVjXHViMmM4XHVjNTQ4IFx1YjEyNFx1ZDJiOFx1YzZjY1x1ZDA2Y1x1YzVkMFx1YzExYywgXHVhYzAwXHVjOTExXHVjZTU4IFx1ZDU2OVx1Yzc3NCBcdWNkNWNcdWIzMDBcdWM3NzgmbmJzcDtcdWIyZThcdWMyMWMgXHVhY2JkXHViODVjXHVjNzU4IFx1YWMwMFx1YzkxMVx1Y2U1OCBcdWQ1NjlcdWM3NDQgXHVjZDljXHViODI1XHVkNTU4XHViNzdjLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjODE1XHVjODEwXHVjNzU4IFx1YWMxY1x1YzIxOCBuXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDMgJmxlOyBuICZsZTsgMjUwKTxcL3A+XHJcblxyXG48cD5cdWM3NzRcdWQ2YzQgMyhuLTIpIFx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHVhYzA0XHVjMTIwXHVjNzU4IFx1YzgxNVx1YmNmNCBhPHN1Yj5pPFwvc3ViPiwgYjxzdWI+aTxcL3N1Yj4sIGM8c3ViPmk8XC9zdWI+IFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1ZDU3NFx1YjJmOSBcdWFjMDRcdWMxMjBcdWM3NzQgXHViNDUwIFx1YzgxNVx1YzgxMCBhPHN1Yj5pPFwvc3ViPiwgYjxzdWI+aTxcL3N1Yj4gXHViOTdjIGM8c3ViPmk8XC9zdWI+XHVjNzU4IFx1YWMwMFx1YzkxMVx1Y2U1OFx1Yjg1YyBcdWM3ODdcdWIyOTRcdWIyZTRcdWIyOTQgXHVhYzgzXHVjNzc0XHViMmU0LiAoMSAmbGU7IGE8c3ViPmk8XC9zdWI+LCBiPHN1Yj5pPFwvc3ViPiAmbGU7IG4sIDAgJmxlOyBjPHN1Yj5pPFwvc3ViPiAmbGU7IDEwPHN1cD42PFwvc3VwPik8XC9wPlxyXG5cclxuPHA+XHVjOGZjXHVjNWI0XHVjOWM0IFx1YWRmOFx1Yjc5OFx1ZDUwNFx1YjI5NCBcdWM1NDRcdWQzZjRcdWI4NWNcdWIyYzhcdWM1NDggXHViMTI0XHVkMmI4XHVjNmNjXHVkMDZjXHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMFx1YzkxMVx1Y2U1OCBcdWQ1NjlcdWM3NzQgXHVjZDVjXHViMzAwXHVjNzc4Jm5ic3A7XHViMmU4XHVjMjFjIFx1YWNiZFx1Yjg1Y1x1Yzc1OCBcdWFjMDBcdWM5MTFcdWNlNTggXHVkNTY5XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1Yjc3Yy48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIxNzgyNCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkFwb2xsb25pYW4gTmV0d29yayIsImRlc2NyaXB0aW9uIjoiPHA+QW4gQXBvbGxvbmlhbiBuZXR3b3JrIGlzIGFuIHVuZGlyZWN0ZWQgZ3JhcGggZm9ybWVkIGJ5IHJlY3Vyc2l2ZWx5IHN1YmRpdmlkaW5nIGEgdHJpYW5nbGUgaW50byB0aHJlZSBzbWFsbGVyIHRyaWFuZ2xlcy48XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJodHRwczpcL1wvdXBsb2FkLmFjbWljcGMubmV0XC8wYTc1MmQzMC0yYzQzLTQyOWMtYmFkNy0wMDRhZDRkNmI1NDVcLy1cL3ByZXZpZXdcL1wiIHN0eWxlPVwid2lkdGg6IDI2MnB4OyBoZWlnaHQ6IDIyN3B4O1wiIFwvPjxcL3A+XHJcblxyXG48cD5ZdWhhbyBEdSBoYXMgYW4gQXBvbGxvbmlhbiBuZXR3b3JrIHdpdGggd2VpZ2h0ZWQgZWRnZXMuIEFuZCBoZSBrbm93cyBob3cgdG8gZmluZCBhIHNpbXBsZSBwYXRoIHdpdGggdGhlIGxhcmdlc3QgcG9zc2libGUgc3VtIG9mIGVkZ2Ugd2VpZ2h0cy4gQ2FuIHlvdSBmaW5kIGl0IHRvbz88XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIHRoZSBpbnB1dCBjb250YWlucyBvbmUgaW50ZWdlciBuOiB0aGUgbnVtYmVyIG9mIHZlcnRpY2VzIGluIFl1aGFvJnJzcXVvO3MgQXBvbGxvbmlhbiBuZXR3b3JrICgzICZsZTsgbiAmbGU7IDI1MCkuPFwvcD5cclxuXHJcbjxwPlRoZSBuZXh0IDMobiAmbWludXM7IDIpIGxpbmVzIGNvbnRhaW4gYSBkZXNjcmlwdGlvbiBvZiB0aGUgZWRnZXMgb2YgdGhlIGdyYXBoLiBFYWNoIG9mIHRoZXNlIGxpbmVzIGNvbnRhaW5zIHRocmVlIGludGVnZXJzIGE8c3ViPmk8XC9zdWI+LCBiPHN1Yj5pPFwvc3ViPiwgYzxzdWI+aTxcL3N1Yj4sIGRlc2NyaWJpbmcgYW4gZWRnZSBiZXR3ZWVuIHZlcnRpY2VzIGFpIGFuZCBiaSB3aXRoIHdlaWdodCBjPHN1Yj5pPFwvc3ViPiAoMSAmbGU7IGE8c3ViPmk8XC9zdWI+LCBiPHN1Yj5pPFwvc3ViPiAmbGU7IG4sIGE8c3ViPmk8XC9zdWI+ICZuZTsgYjxzdWI+aTxcL3N1Yj4sIDAgJmxlOyBjPHN1Yj5pPFwvc3ViPiAmbGU7IDEwPHN1cD42PFwvc3VwPikuPFwvcD5cclxuXHJcbjxwPkl0IGlzIGd1YXJhbnRlZWQgdGhhdCB0aGUgZ2l2ZW4gZ3JhcGggaXMgYW4gQXBvbGxvbmlhbiBuZXR3b3JrLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk91dHB1dCBvbmUgaW50ZWdlcjogdGhlIGxhcmdlc3Qgc3VtIG9mIGVkZ2Ugd2VpZ2h0cyBvbiBhIHNpbXBsZSBwYXRoIGluIFl1aGFvJnJzcXVvO3MgQXBvbGxvbmlhbiBuZXR3b3JrLjxcL3A+XHJcbiIsImhpbnQiOiI8cD5JbiB0aGUgZmlyc3QgZXhhbXBsZSwgb25lIG9mIHRoZSBvcHRpbWFsIHBhdGhzIGlzIDIgJnJhcnI7IDMgJnJhcnI7IDEuPFwvcD5cclxuXHJcbjxwPkluIHRoZSBzZWNvbmQgZXhhbXBsZSwgb25lIG9mIHRoZSBvcHRpbWFsIHBhdGhzIGlzIDUgJnJhcnI7IDIgJnJhcnI7IDEgJnJhcnI7IDcgJnJhcnI7IDEwICZyYXJyOyA4ICZyYXJyOyA5ICZyYXJyOyAzICZyYXJyOyA2ICZyYXJyOyA0LjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

Camp > Petrozavodsk Programming Camp > Summer 2019 > Day 2: 300iq Contest 2 A번

Contest > Open Cup > 2019/2020 Season > Stage 1: Grand Prix of Kazan A번

  • 문제를 만든 사람: 300iq
  • 문제를 번역한 사람: koosaga
(追記) (追記ここまで)

출처

대학교 대회

  • 사업자 등록 번호: 541-88-00682
  • 대표자명: 최백준
  • 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
  • 전화번호: 02-521-0487 (이메일로 연락 주세요)
  • 이메일: contacts@startlink.io
  • 통신판매신고번호: 제 2017-서울서초-2193 호

AltStyle によって変換されたページ (->オリジナル) /