문제
$N\times N$ 크기의 행렬 $D$가 있다. 당신은 정점이 $N$개이고 아래 조건들을 만족하는 무방향 연결 그래프를 구성해야 한다. 각 정점은 1ドル$부터 $N$까지 번호가 매겨져 있으며, 각 간선에는 양의 정수 가중치를 원하는 대로 부여할 수 있다.
- 모든 정점 쌍 $(u,v)$에 대해, $u$와 $v$ 사이의 최단 경로의 길이는 $D_{u,v}$이다.
- 모든 간선의 가중치의 합은 가능한 최소여야 한다.
조건을 만족하는 그래프가 존재하는지 판별하고, 있다면 그 중 아무거나 하나를 출력하라.
출력
문제의 조건을 만족하는 그래프가 존재하지 않는다면, $-1$을 출력한다.
조건을 만족하는 그래프가 존재한다면,
- 첫 번째 줄에 간선의 개수를 나타내는 정수 $M$을 출력한다.
- 다음 $M$개 줄 중 $i$번째 줄에 세 정수 $u_i,ドル $v_i,ドル $c_i$를 공백으로 구분하여 출력한다. 이것은 $i$번 간선이 두 정점 $u_i$와 $v_i$를 잇고 가중치가 $c_i$라는 것을 나타낸다.
- 같은 쌍의 정점을 연결하는 간선은 최대 하나여야 하고, 각 간선의 가중치는 10ドル^9$ 이하여야 한다.
제한
- 2ドル\leq N\leq 300$
- $D_{i,i}=0$ (1ドル\le i\le N$)
- 1ドル\leq D_{i,j}=D_{j,i}\leq 10^9$ (1ドル\le i<j\le N$)
- 1ドル\leq u_i,v_i\leq N$ (1ドル\le i\le M$)
- $u_i\neq v_i$ (1ドル\le i\le M$)
- 1ドル\leq c_i\leq 10^9$ (1ドル\le i\le M$)
- 같은 쌍의 정점을 연결하는 간선은 최대 하나여야 한다.
서브태스크
| 번호 | 배점 | 제한 | | 1 | 9 | 이 서브태스크에서는 조건을 만족하는 그래프가 존재하는지만 판별해도 된다. 즉, 채점 프로그램은 출력이 $-1$인지 아닌지의 여부만 확인한다.
|
| 2 | 19 | $N \leq 50$
|
| 3 | 72 | 추가적인 제약 조건이 없다.
|
W3sicHJvYmxlbV9pZCI6IjMxODE1IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiQ29uc3RydWN0IGEgR3JhcGgiLCJkZXNjcmlwdGlvbiI6IjxwPiROXFx0aW1lcyBOJCBcdWQwNmNcdWFlMzBcdWM3NTggXHVkNTg5XHViODJjICREJFx1YWMwMCBcdWM3ODhcdWIyZTQuIFx1YjJmOVx1YzJlMFx1Yzc0MCBcdWM4MTVcdWM4MTBcdWM3NzQgJE4kXHVhYzFjXHVjNzc0XHVhY2UwIFx1YzU0NFx1Yjc5OCBcdWM4NzBcdWFjNzRcdWI0ZTRcdWM3NDQgXHViOWNjXHVjODcxXHVkNTU4XHViMjk0IFx1YmIzNFx1YmMyOVx1ZDVhNSBcdWM1ZjBcdWFjYjAgXHVhZGY4XHViNzk4XHVkNTA0XHViOTdjIFx1YWQ2Y1x1YzEzMVx1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1YWMwMSBcdWM4MTVcdWM4MTBcdWM3NDAgJDEkXHViZDgwXHVkMTMwICROJFx1YWU0Y1x1YzljMCBcdWJjODhcdWQ2MzhcdWFjMDAgXHViOWU0XHVhY2E4XHVjODM4IFx1Yzc4OFx1YzczY1x1YmE3MCwgXHVhYzAxIFx1YWMwNFx1YzEyMFx1YzVkMFx1YjI5NCBcdWM1OTFcdWM3NTggXHVjODE1XHVjMjE4IFx1YWMwMFx1YzkxMVx1Y2U1OFx1Yjk3YyBcdWM2ZDBcdWQ1NThcdWIyOTQgXHViMzAwXHViODVjIFx1YmQ4MFx1YzVlY1x1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPlx1YmFhOFx1YjRlMCBcdWM4MTVcdWM4MTAgXHVjMzBkICQodSx2KSRcdWM1ZDAgXHViMzAwXHVkNTc0LCAkdSRcdWM2NDAgJHYkIFx1YzBhY1x1Yzc3NFx1Yzc1OCBcdWNkNWNcdWIyZTggXHVhY2JkXHViODVjXHVjNzU4IFx1YWUzOFx1Yzc3NFx1YjI5NCAkRF97dSx2fSRcdWM3NzRcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YmFhOFx1YjRlMCBcdWFjMDRcdWMxMjBcdWM3NTggXHVhYzAwXHVjOTExXHVjZTU4XHVjNzU4IFx1ZDU2OVx1Yzc0MCBcdWFjMDBcdWIyYTVcdWQ1NWMgXHVjZDVjXHVjMThjXHVjNWVjXHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5cdWM4NzBcdWFjNzRcdWM3NDQgXHViOWNjXHVjODcxXHVkNTU4XHViMjk0IFx1YWRmOFx1Yjc5OFx1ZDUwNFx1YWMwMCBcdWM4NzRcdWM3YWNcdWQ1NThcdWIyOTRcdWM5YzAgXHVkMzEwXHViY2M0XHVkNTU4XHVhY2UwLCBcdWM3ODhcdWIyZTRcdWJhNzQgXHVhZGY4IFx1YzkxMSBcdWM1NDRcdWJiMzRcdWFjNzBcdWIwOTggXHVkNTU4XHViMDk4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1Yjc3Yy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzgxNVx1YzgxMFx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IFx1YzgxNVx1YzIxOCAkTiRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgJE4kXHVhYzFjIFx1YzkwNCBcdWM5MTEgJGkkXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCAkTiRcdWFjMWNcdWM3NTggXHVjODE1XHVjMjE4ICREX3tpLDF9LERfe2ksMn0sXFxsZG90cyAsRF97aSxOfSRcdWM3NzQgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxOFx1YzViNCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHViYjM4XHVjODFjXHVjNzU4IFx1Yzg3MFx1YWM3NFx1Yzc0NCBcdWI5Y2NcdWM4NzFcdWQ1NThcdWIyOTQgXHVhZGY4XHViNzk4XHVkNTA0XHVhYzAwIFx1Yzg3NFx1YzdhY1x1ZDU1OFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTRcdWJhNzQsICQtMSRcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM4NzBcdWFjNzRcdWM3NDQgXHViOWNjXHVjODcxXHVkNTU4XHViMjk0IFx1YWRmOFx1Yjc5OFx1ZDUwNFx1YWMwMCBcdWM4NzRcdWM3YWNcdWQ1NWNcdWIyZTRcdWJhNzQsPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+XHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVhYzA0XHVjMTIwXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgXHVjODE1XHVjMjE4ICRNJFx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YjJlNFx1Yzc0YyAkTSRcdWFjMWMgXHVjOTA0IFx1YzkxMSAkaSRcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzEzOCBcdWM4MTVcdWMyMTggJHVfaSQsICR2X2kkLCAkY19pJFx1Yjk3YyBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHVkNTU4XHVjNWVjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVjNzc0XHVhYzgzXHVjNzQwICRpJFx1YmM4OCBcdWFjMDRcdWMxMjBcdWM3NzQgXHViNDUwIFx1YzgxNVx1YzgxMCAkdV9pJFx1YzY0MCAkdl9pJFx1Yjk3YyBcdWM3ODdcdWFjZTAgXHVhYzAwXHVjOTExXHVjZTU4XHVhYzAwICRjX2kkXHViNzdjXHViMjk0IFx1YWM4M1x1Yzc0NCBcdWIwOThcdWQwYzBcdWIwYjhcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YWMxOVx1Yzc0MCBcdWMzMGRcdWM3NTggXHVjODE1XHVjODEwXHVjNzQ0IFx1YzVmMFx1YWNiMFx1ZDU1OFx1YjI5NCBcdWFjMDRcdWMxMjBcdWM3NDAgXHVjZDVjXHViMzAwIFx1ZDU1OFx1YjA5OFx1YzVlY1x1YzU3YyBcdWQ1NThcdWFjZTAsIFx1YWMwMSBcdWFjMDRcdWMxMjBcdWM3NTggXHVhYzAwXHVjOTExXHVjZTU4XHViMjk0ICQxMF45JCBcdWM3NzRcdWQ1NThcdWM1ZWNcdWM1N2MgXHVkNTVjXHViMmU0LjxcL2xpPlxyXG48XC91bD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIiwibGltaXQiOiI8dWw+XHJcblx0PGxpPiQyXFxsZXEgTlxcbGVxIDMwMCQ8XC9saT5cclxuXHQ8bGk+JERfe2ksaX09MCQgKCQxXFxsZSBpXFxsZSBOJCk8XC9saT5cclxuXHQ8bGk+JDFcXGxlcSBEX3tpLGp9PURfe2osaX1cXGxlcSAxMF45JCAoJDFcXGxlIGkmbHQ7alxcbGUgTiQpPFwvbGk+XHJcblx0PGxpPiQxXFxsZXEgdV9pLHZfaVxcbGVxIE4kICgkMVxcbGUgaVxcbGUgTSQpPFwvbGk+XHJcblx0PGxpPiR1X2lcXG5lcSB2X2kkICgkMVxcbGUgaVxcbGUgTSQpPFwvbGk+XHJcblx0PGxpPiQxXFxsZXEgY19pXFxsZXEgMTBeOSQgKCQxXFxsZSBpXFxsZSBNJCk8XC9saT5cclxuXHQ8bGk+XHVhYzE5XHVjNzQwIFx1YzMwZFx1Yzc1OCBcdWM4MTVcdWM4MTBcdWM3NDQgXHVjNWYwXHVhY2IwXHVkNTU4XHViMjk0IFx1YWMwNFx1YzEyMFx1Yzc0MCBcdWNkNWNcdWIzMDAgXHVkNTU4XHViMDk4XHVjNWVjXHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9saT5cclxuPFwvdWw+XHJcbiIsInN1YnRhc2sxIjoiPHA+XHVjNzc0IFx1YzExY1x1YmUwY1x1ZDBkY1x1YzJhNFx1ZDA2Y1x1YzVkMFx1YzExY1x1YjI5NCBcdWM4NzBcdWFjNzRcdWM3NDQgXHViOWNjXHVjODcxXHVkNTU4XHViMjk0IFx1YWRmOFx1Yjc5OFx1ZDUwNFx1YWMwMCBcdWM4NzRcdWM3YWNcdWQ1NThcdWIyOTRcdWM5YzBcdWI5Y2MgXHVkMzEwXHViY2M0XHVkNTc0XHViM2M0IFx1YjQxY1x1YjJlNC4gXHVjOTg5LCBcdWNjNDRcdWM4MTAgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQwIFx1Y2Q5Y1x1YjgyNVx1Yzc3NCAkLTEkXHVjNzc4XHVjOWMwIFx1YzU0NFx1YjJjY1x1YzljMFx1Yzc1OCBcdWM1ZWNcdWJkODBcdWI5Y2MgXHVkNjU1XHVjNzc4XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsInN1YnRhc2syIjoiPHA+JE4gXFxsZXEgNTAkPFwvcD5cclxuIiwic3VidGFzazMiOiI8cD5cdWNkOTRcdWFjMDBcdWM4MDFcdWM3NzggXHVjODFjXHVjNTdkIFx1Yzg3MFx1YWM3NFx1Yzc3NCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuIn0seyJwcm9ibGVtX2lkIjoiMzE4MTUiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJDb25zdHJ1Y3QgYSBHcmFwaCIsImRlc2NyaXB0aW9uIjoiPHA+WW91IGFyZSBnaXZlbiBhbiAkTlxcdGltZXMgTiQgc3F1YXJlIG1hdHJpeCAkRCQuIFlvdXIgdGFzayBpcyB0byBjb25zdHJ1Y3QgYW4gdW5kaXJlY3RlZCBjb25uZWN0ZWQgZ3JhcGggd2l0aCAkTiQgdmVydGljZXMgdGhhdCBmdWxmaWxscyB0aGUgZm9sbG93aW5nIGNvbmRpdGlvbnMuIEVhY2ggdmVydGV4IGlzIG51bWJlcmVkIGZyb20gJDEkIHRvICROJCwgYW5kIHlvdSBtYXkgYXNzaWduIHBvc2l0aXZlIGludGVnZXIgd2VpZ2h0cyB0byBlYWNoIGVkZ2UgYXMgZGVzaXJlZC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5Gb3IgYWxsIHBhaXJzIG9mIHZlcnRpY2VzICQodSx2KSQsIHRoZSBsZW5ndGggb2YgdGhlIHNob3J0ZXN0IHBhdGggYmV0d2VlbiAkdSQgYW5kICR2JCBtdXN0IGJlIGVxdWFsIHRvICREX3t1LHZ9JC48XC9saT5cclxuXHQ8bGk+VGhlIHRvdGFsIHN1bSBvZiBlZGdlIHdlaWdodHMgbXVzdCBiZSBtaW5pbWl6ZWQuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+RGV0ZXJtaW5lIHdoZXRoZXIgc3VjaCBhIGdyYXBoIGV4aXN0cywgYW5kIGlmIHNvLCBwcmludCBhbnkgZ3JhcGggdGhhdCBzYXRpc2ZpZXMgdGhlc2UgY29uZGl0aW9ucy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIGNvbnRhaW5zIGFuIGludGVnZXIgJE4kICZtZGFzaDsgdGhlIG51bWJlciBvZiB2ZXJ0aWNlcy48XC9wPlxyXG5cclxuPHA+VGhlICRpJC10aCBvZiB0aGUgbmV4dCAkTiQgbGluZXMgY29udGFpbnMgJE4kIGludGVnZXJzICREX3tpLDF9LERfe2ksMn0sXFxsZG90cyAsRF97aSxOfSQgc2VwYXJhdGVkIGJ5IGEgc3BhY2UuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+SWYgbm8gZ3JhcGggc2F0aXNmaWVzIHRoZSBjb25kaXRpb25zLCBwcmludCAkLTEkLjxcL3A+XHJcblxyXG48cD5JZiB0aGVyZSBleGlzdHMgYSBncmFwaCB0aGF0IHNhdGlzZmllcyB0aGUgY29uZGl0aW9uczo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5PbiB0aGUgZmlyc3QgbGluZSwgcHJpbnQgYW4gaW50ZWdlciAkTSQgJm1kYXNoOyB0aGUgbnVtYmVyIG9mIGVkZ2VzLjxcL2xpPlxyXG5cdDxsaT5PbiB0aGUgJGkkLXRoIG9mIHRoZSBuZXh0ICRNJCBsaW5lcywgcHJpbnQgdGhyZWUgaW50ZWdlcnMgJHVfaSQsICR2X2kkLCAkY19pJCwgc2VwYXJhdGVkIGJ5IGEgc3BhY2UuIFRoZXNlIGludGVnZXJzIG1lYW4gdGhhdCB0aGUgJGkkLXRoIGVkZ2UgY29ubmVjdHMgdHdvIHZlcnRpY2VzICR1X2kkIGFuZCAkdl9pJCBhbmQgaXRzIHdlaWdodCBpcyAkY19pJC48XC9saT5cclxuXHQ8bGk+VGhlcmUgc2hvdWxkIGJlIGF0IG1vc3Qgb25lIGVkZ2UgZm9yIGVhY2ggcGFpciBvZiB2ZXJ0aWNlcywgYW5kIHRoZSB3ZWlnaHQgb2YgZWFjaCBlZGdlIHNob3VsZCBub3QgZXhjZWVkICQxMF45JC48XC9saT5cclxuPFwvdWw+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2giLCJsaW1pdCI6Ijx1bD5cclxuXHQ8bGk+JDJcXGxlcSBOXFxsZXEgMzAwJDxcL2xpPlxyXG5cdDxsaT4kRF97aSxpfT0wJCAoJDFcXGxlIGlcXGxlIE4kKTxcL2xpPlxyXG5cdDxsaT4kMVxcbGVxIERfe2ksan09RF97aixpfVxcbGVxIDEwXjkkICgkMVxcbGUgaSZsdDtqXFxsZSBOJCk8XC9saT5cclxuXHQ8bGk+JDFcXGxlcSB1X2ksdl9pXFxsZXEgTiQgKCQxXFxsZSBpXFxsZSBNJCk8XC9saT5cclxuXHQ8bGk+JHVfaVxcbmVxIHZfaSQgKCQxXFxsZSBpXFxsZSBNJCk8XC9saT5cclxuXHQ8bGk+JDFcXGxlcSBjX2lcXGxlcSAxMF45JCAoJDFcXGxlIGlcXGxlIE0kKTxcL2xpPlxyXG5cdDxsaT5UaGVyZSBzaG91bGQgYmUgYXQgbW9zdCBvbmUgZWRnZSBjb25uZWN0aW5nIGEgcGFpciBvZiB2ZXJ0aWNlcy48XC9saT5cclxuPFwvdWw+XHJcbiIsInN1YnRhc2sxIjoiPHA+SW4gdGhpcyBzdWJ0YXNrLCB5b3Ugb25seSBuZWVkIHRvIGRldGVybWluZSB3aGV0aGVyIHRoZXJlIGV4aXN0cyBhIGdyYXBoIHNhdGlzZnlpbmcgdGhlIGNvbmRpdGlvbnMuIEluIG90aGVyIHdvcmRzLCB0aGUgY2hlY2tlciBvbmx5IGNoZWNrcyB3aGV0aGVyIHRoZSBvdXRwdXQgaXMgJC0xJCBvciBub3QuPFwvcD5cclxuIiwic3VidGFzazIiOiI8cD4kTiBcXGxlcSA1MCQ8XC9wPlxyXG4iLCJzdWJ0YXNrMyI6IjxwPk5vIGFkZGl0aW9uYWwgY29uc3RyYWludHMuPFwvcD5cclxuIn1d