시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 3911 915 675 23.156%

문제

이 문제는 삼각 그래프의 가장 위쪽 가운데 정점에서 가장 아래쪽 가운데 정점으로 가는 최단 경로를 찾는 문제이다.

삼각 그래프는 사이클이 없는 그래프로 N ≥ 2 개의 행과 3열로 이루어져 있다. 삼각 그래프는 보통 그래프와 다르게 간선이 아닌 정점에 비용이 있다. 어떤 경로의 비용은 그 경로에서 지나간 정점의 비용의 합이다.

오른쪽 그림은 N = 4인 삼각 그래프이고, 가장 위쪽 가운데 정점에서 가장 아래쪽 가운데 정점으로 경로 중 아래로만 가는 경로의 비용은 7+13+3+6 = 29가 된다. 삼각 그래프의 간선은 항상 오른쪽 그림과 같은 형태로 연결되어 있다.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 그래프의 행의 개수 N이 주어진다. (2 ≤ N ≤ 100,000) 다음 N개 줄에는 그래프의 i번째 행에 있는 정점의 비용이 순서대로 주어진다. 비용은 정수이며, 비용의 제곱은 1,000,000보다 작다.

입력의 마지막 줄에는 0이 하나 주어진다.

출력

각 테스트 케이스에 대해서, 가장 위쪽 가운데 정점에서 가장 아래쪽 가운데 정점으로 가는 최소 비용을 테스트 케이스 번호와 아래와 같은 형식으로 출력한다.

k. n

k는 테스트 케이스 번호, n은 최소 비용이다.

예제 입력 1

4
13 7 5
7 13 6
14 3 12
15 6 16
0

예제 출력 1

1. 22
W3sicHJvYmxlbV9pZCI6IjQ4ODMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMwYmNcdWFjMDEgXHVhZGY4XHViNzk4XHVkNTA0IiwiZGVzY3JpcHRpb24iOiI8cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3RyaWdyYXBoLnBuZ1wiIHN0eWxlPVwiZmxvYXQ6cmlnaHQ7IGhlaWdodDozNDJweDsgd2lkdGg6MjYxcHhcIiBcLz5cdWM3NzQgXHViYjM4XHVjODFjXHViMjk0IFx1YzBiY1x1YWMwMSBcdWFkZjhcdWI3OThcdWQ1MDRcdWM3NTggXHVhYzAwXHVjN2E1IFx1YzcwNFx1Y2FiZCBcdWFjMDBcdWM2YjRcdWIzNzAgXHVjODE1XHVjODEwXHVjNWQwXHVjMTFjIFx1YWMwMFx1YzdhNSBcdWM1NDRcdWI3OThcdWNhYmQgXHVhYzAwXHVjNmI0XHViMzcwIFx1YzgxNVx1YzgxMFx1YzczY1x1Yjg1YyBcdWFjMDBcdWIyOTQgXHVjZDVjXHViMmU4IFx1YWNiZFx1Yjg1Y1x1Yjk3YyBcdWNjM2VcdWIyOTQgXHViYjM4XHVjODFjXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMwYmNcdWFjMDEgXHVhZGY4XHViNzk4XHVkNTA0XHViMjk0IFx1YzBhY1x1Yzc3NFx1ZDA3NFx1Yzc3NCBcdWM1YzZcdWIyOTQgXHVhZGY4XHViNzk4XHVkNTA0XHViODVjIE4gJmdlOyAyIFx1YWMxY1x1Yzc1OCBcdWQ1ODlcdWFjZmMgM1x1YzVmNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWMwYmNcdWFjMDEgXHVhZGY4XHViNzk4XHVkNTA0XHViMjk0IFx1YmNmNFx1ZDFiNSBcdWFkZjhcdWI3OThcdWQ1MDRcdWM2NDAgXHViMmU0XHViOTc0XHVhYzhjIFx1YWMwNFx1YzEyMFx1Yzc3NCBcdWM1NDRcdWIyY2MgXHVjODE1XHVjODEwXHVjNWQwIFx1YmU0NFx1YzZhOVx1Yzc3NCBcdWM3ODhcdWIyZTQuIFx1YzViNFx1YjVhNCBcdWFjYmRcdWI4NWNcdWM3NTggXHViZTQ0XHVjNmE5XHVjNzQwIFx1YWRmOCBcdWFjYmRcdWI4NWNcdWM1ZDBcdWMxMWMgXHVjOWMwXHViMDk4XHVhYzA0IFx1YzgxNVx1YzgxMFx1Yzc1OCBcdWJlNDRcdWM2YTlcdWM3NTggXHVkNTY5XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM2MjRcdWI5NzhcdWNhYmQgXHVhZGY4XHViOWJjXHVjNzQwIE4gPSA0XHVjNzc4IFx1YzBiY1x1YWMwMSBcdWFkZjhcdWI3OThcdWQ1MDRcdWM3NzRcdWFjZTAsIFx1YWMwMFx1YzdhNSBcdWM3MDRcdWNhYmQgXHVhYzAwXHVjNmI0XHViMzcwIFx1YzgxNVx1YzgxMFx1YzVkMFx1YzExYyBcdWFjMDBcdWM3YTUgXHVjNTQ0XHViNzk4XHVjYWJkIFx1YWMwMFx1YzZiNFx1YjM3MCBcdWM4MTVcdWM4MTBcdWM3M2NcdWI4NWMgXHVhY2JkXHViODVjIFx1YzkxMSBcdWM1NDRcdWI3OThcdWI4NWNcdWI5Y2MgXHVhYzAwXHViMjk0IFx1YWNiZFx1Yjg1Y1x1Yzc1OCZuYnNwO1x1YmU0NFx1YzZhOVx1Yzc0MCA3KzEzKzMrNiA9IDI5XHVhYzAwIFx1YjQxY1x1YjJlNC4gXHVjMGJjXHVhYzAxIFx1YWRmOFx1Yjc5OFx1ZDUwNFx1Yzc1OCBcdWFjMDRcdWMxMjBcdWM3NDAgXHVkNTZkXHVjMGMxIFx1YzYyNFx1Yjk3OFx1Y2FiZCBcdWFkZjhcdWI5YmNcdWFjZmMgXHVhYzE5XHVjNzQwIFx1ZDYxNVx1ZDBkY1x1Yjg1YyBcdWM1ZjBcdWFjYjBcdWI0MThcdWM1YjQgXHVjNzg4XHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzQwIFx1YzVlY1x1YjdlYyBcdWFjMWNcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YWRmOFx1Yjc5OFx1ZDUwNFx1Yzc1OCBcdWQ1ODlcdWM3NTggXHVhYzFjXHVjMjE4IE5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMiAmbGU7IE4gJmxlOyAxMDAsMDAwKSBcdWIyZTRcdWM3NGMgTlx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhZGY4XHViNzk4XHVkNTA0XHVjNzU4IGlcdWJjODhcdWM5ZjggXHVkNTg5XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWM4MTVcdWM4MTBcdWM3NTggXHViZTQ0XHVjNmE5XHVjNzc0IFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YmU0NFx1YzZhOVx1Yzc0MCBcdWM4MTVcdWMyMThcdWM3NzRcdWJhNzAsIFx1YmU0NFx1YzZhOVx1Yzc1OCBcdWM4MWNcdWFjZjFcdWM3NDAgMSwwMDAsMDAwXHViY2Y0XHViMmU0IFx1Yzc5MVx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzg1XHViODI1XHVjNzU4IFx1YjljOFx1YzljMFx1YjljOSBcdWM5MDRcdWM1ZDBcdWIyOTQgMFx1Yzc3NCBcdWQ1NThcdWIwOTggXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYywgXHVhYzAwXHVjN2E1IFx1YzcwNFx1Y2FiZCBcdWFjMDBcdWM2YjRcdWIzNzAgXHVjODE1XHVjODEwXHVjNWQwXHVjMTFjIFx1YWMwMFx1YzdhNSBcdWM1NDRcdWI3OThcdWNhYmQgXHVhYzAwXHVjNmI0XHViMzcwIFx1YzgxNVx1YzgxMFx1YzczY1x1Yjg1YyBcdWFjMDBcdWIyOTQgXHVjZDVjXHVjMThjIFx1YmU0NFx1YzZhOVx1Yzc0NCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0IFx1YmM4OFx1ZDYzOFx1YzY0MCBcdWM1NDRcdWI3OThcdWM2NDAgXHVhYzE5XHVjNzQwIFx1ZDYxNVx1YzJkZFx1YzczY1x1Yjg1YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwcmU+XHJcbmsuIG48XC9wcmU+XHJcblxyXG48cD5rXHViMjk0IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTQgXHViYzg4XHVkNjM4LCBuXHVjNzQwIFx1Y2Q1Y1x1YzE4YyBcdWJlNDRcdWM2YTlcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNDg4MyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlRyaSBncmFwaHMiLCJkZXNjcmlwdGlvbiI6IjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvdHJpZ3JhcGgucG5nXCIgc3R5bGU9XCJmbG9hdDpyaWdodDsgaGVpZ2h0OjM0MnB4OyB3aWR0aDoyNjFweFwiIFwvPkhlcmUmcnNxdW87cyBhIHNpbXBsZSBncmFwaCBwcm9ibGVtOiBGaW5kIHRoZSBzaG9ydGVzdCBwYXRoIGZyb20gdGhlIHRvcC1taWRkbGUgdmVydGV4IHRvIHRoZSBib3R0b20tbWlkZGxlIHZlcnRleCBpbiBhIGdpdmVuIHRyaS1ncmFwaC4gQSB0cmktZ3JhcGggaXMgYW4gYWN5Y2xpYyBncmFwaCBvZiAoTiAmZ2U7IDIpIHJvd3MgYW5kIGV4YWN0bHkgMyBjb2x1bW5zLiBVbmxpa2UgcmVndWxhciBncmFwaHMsIHRoZSBjb3N0cyBpbiBhIHRyaS1ncmFwaCBhcmUgYXNzb2NpYXRlZCB3aXRoIHRoZSB2ZXJ0aWNlcyByYXRoZXIgdGhhbiB0aGUgZWRnZXMuIFNvLCBjb25zaWRlcmluZyB0aGUgZXhhbXBsZSBvbiB0aGUgcmlnaHQgd2l0aCBOID0gNCwgdGhlIGNvc3Qgb2YgZ29pbmcgc3RyYWlnaHQgZG93biBmcm9tIHRoZSB0b3AgdG8gYm90dG9tIGFsb25nIHRoZSBtaWRkbGUgdmVydGljZXMgaXMgNysgMTMrIDMrIDYgPSAyOS4gVGhlIGxheW91dCBvZiB0aGUgZGlyZWN0aW9uYWwgZWRnZXMgaW4gdGhlIGdyYXBoIGFyZSBhbHdheXMgdGhlIHNhbWUgYXMgaWxsdXN0cmF0ZWQgaW4gdGhlIFx1ZmIwMWd1cmUuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5Zb3VyIHByb2dyYW0gd2lsbCBiZSB0ZXN0ZWQgb24gb25lIG9yIG1vcmUgdGVzdCBjYXNlcy4gRWFjaCB0ZXN0IGNhc2UgaXMgc3BlY2lcdWZiMDFlZCB1c2luZyBOICsgMSBsaW5lcyB3aGVyZSB0aGUgXHVmYjAxcnN0IGxpbmUgc3BlY2lcdWZiMDFlcyBhIHNpbmdsZSBpbnRlZ2VyICgyICZsZTsgTiAmbGU7IDEwMCwwMDApIGRlbm90aW5nIHRoZSBudW1iZXIgb2Ygcm93cyBpbiB0aGUgZ3JhcGguIE4gbGluZXMgZm9sbG93LCBlYWNoIHNwZWNpZnlpbmcgdGhyZWUgaW50ZWdlcnMgcmVwcmVzZW50aW5nIHRoZSBjb3N0IG9mIHRoZSB2ZXJ0aWNlcyBvbiB0aGUgaXRoIHJvdyBmcm9tIGxlZnQgdG8gcmlnaHQuIFRoZSBzcXVhcmUgb2YgZWFjaCBjb3N0IHZhbHVlIGlzIGxlc3MgdGhhbiAxLDAwMCwwMDAuPFwvcD5cclxuXHJcbjxwPlRoZSBsYXN0IGNhc2UgaXMgZm9sbG93ZWQgYnkgYSBsaW5lIHdpdGggYSBzaW5nbGUgemVyby48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2UsIHByaW50IHRoZSBmb2xsb3dpbmcgbGluZTo8XC9wPlxyXG5cclxuPHByZT5cclxuay5cdTAwMDIgbjxcL3ByZT5cclxuXHJcbjxwPldoZXJlIGsgaXMgdGhlIHRlc3QgY2FzZSBudW1iZXIgKHN0YXJ0aW5nIGF0IG9uZSwpIGFuZCBuIGlzIHRoZSBsZWFzdCBjb3N0IHRvIGdvIGZyb20gdGhlIHRvcC1taWRkbGUgdmVydGV4IHRvIHRoZSBib3R0b20tbWlkZGxlIHZlcnRleC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=