시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 256 MB4451539836.296%

문제

사회에 불만이 많은 지용이는 미적분학 교과서를 적당히 찢어서, 한 사람이 충분히 탈 만한 두께 K의 뗏목을 만들었다.

지용이는 이제 A 항구에서 출발해서 무인도 B에 자신의 제국을 건설하기 위해 멀고 먼 여행을 떠날 계획이다. (1 ≤ A, B ≤ N, A ≠ B)

바다에는 N개의 섬이 있고 M개의 바닷길이 있으며, 바닷길 외의 길로는 갈 수가 없으며 지용이는 A에서 B로 가는 동안 섬들을 거쳐가면서 항해할 계획이다.

각 바닷길은 지나가는 데 걸리는 시간 ti, 뗏목을 깎아내리는 정도 hi (cm) 를 가지고 있으며, 만약에 도착하기 전에 뗏목이 0cm 이하의 두께를 가지게 된다면 - 달리 말해서 경로 상의 hi의 합이 K 이상이 된다면, 수영을 못하는 지용이의 목숨을 보장하지 못할수도 있다(!)

지용이는 가장 빠른 시간 내에 A에서 B 지점까지 안전하게 가기를 원한다. 지용이를 도와 그러한 길의 길이를 출력해주자.

입력

첫 번째 줄에는 정수 K, N, M (1 ≤ K ≤ 200; 2 ≤ N ≤ 2000; 1 ≤ M ≤ 10000)이 주어진다.

이 후 M개의 줄에 각 바닷길의 정보가 A, B, ti, hi (1 ≤ A, B ≤ N; 1 ≤ ti ≤ 105; 0 ≤ hi ≤ 200) 형태로 주어진다. 이는 A와 B를 잇는 바닷길이 존재하며, 이 바닷길은 ti의 시간이 걸리며 hi 만큼 뗏목을 깎아내린다는 것을 의미한다. A ≠ B임이 보장된다.

마지막 줄에는 시작점과 도착점인 A, B가 주어진다. (1 ≤ A, B ≤ N; A ≠ B)

출력

지용이가 안전하게 A에서 B에서 항해할 수 있다면 그 때 걸리는 시간을, 그럴 수 없다면 -1을 출력한다.

예제 입력 1

10 4 7
1 2 4 4
1 3 7 2
3 1 8 1
3 2 2 2
4 2 1 6
3 4 1 1
1 4 6 12
1 4

예제 출력 1

7

예제 입력 2

3 3 3
1 2 5 1
3 2 8 2
1 3 1 3
1 3

예제 출력 2

-1
W3sicHJvYmxlbV9pZCI6IjEwNzc2IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjODFjXHVhZDZkIiwiZGVzY3JpcHRpb24iOiI8cD5cdWMwYWNcdWQ2OGNcdWM1ZDAgXHViZDg4XHViOWNjXHVjNzc0IFx1YjljZVx1Yzc0MCBcdWM5YzBcdWM2YTlcdWM3NzRcdWIyOTQgXHViYmY4XHVjODAxXHViZDg0XHVkNTU5IFx1YWQ1MFx1YWNmY1x1YzExY1x1Yjk3YyBcdWM4MDFcdWIyZjlcdWQ3ODggXHVjYzIyXHVjNWI0XHVjMTFjLCBcdWQ1NWMgXHVjMGFjXHViNzhjXHVjNzc0IFx1Y2RhOVx1YmQ4NFx1ZDc4OCBcdWQwYzggXHViOWNjXHVkNTVjIFx1YjQ1MFx1YWVkOCBLXHVjNzU4IFx1YjVjZlx1YmFhOVx1Yzc0NCBcdWI5Y2NcdWI0ZTRcdWM1YzhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzljMFx1YzZhOVx1Yzc3NFx1YjI5NCBcdWM3NzRcdWM4MWMgQSBcdWQ1NmRcdWFkNmNcdWM1ZDBcdWMxMWMgXHVjZDljXHViYzFjXHVkNTc0XHVjMTFjIFx1YmIzNFx1Yzc3OFx1YjNjNCBCXHVjNWQwIFx1Yzc5MFx1YzJlMFx1Yzc1OCBcdWM4MWNcdWFkNmRcdWM3NDQgXHVhYzc0XHVjMTI0XHVkNTU4XHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWJhNDBcdWFjZTAgXHViYTNjIFx1YzVlY1x1ZDU4OVx1Yzc0NCBcdWI1YTBcdWIwYTAgXHVhY2M0XHVkNjhkXHVjNzc0XHViMmU0LiAoMSAmbGU7IEEsIEIgJmxlOyBOLCBBICZuZTsgQik8XC9wPlxyXG5cclxuPHA+XHViYzE0XHViMmU0XHVjNWQwXHViMjk0IE5cdWFjMWNcdWM3NTggXHVjMTJjXHVjNzc0IFx1Yzc4OFx1YWNlMCBNXHVhYzFjXHVjNzU4IFx1YmMxNFx1YjJmN1x1YWUzOFx1Yzc3NCBcdWM3ODhcdWM3M2NcdWJhNzAsIFx1YmMxNFx1YjJmN1x1YWUzOCBcdWM2NzhcdWM3NTggXHVhZTM4XHViODVjXHViMjk0IFx1YWMwOCBcdWMyMThcdWFjMDAgXHVjNWM2XHVjNzNjXHViYTcwIFx1YzljMFx1YzZhOVx1Yzc3NFx1YjI5NCBBXHVjNWQwXHVjMTFjIEJcdWI4NWMgXHVhYzAwXHViMjk0IFx1YjNkOVx1YzU0OCBcdWMxMmNcdWI0ZTRcdWM3NDQgXHVhYzcwXHVjY2QwXHVhYzAwXHViYTc0XHVjMTFjIFx1ZDU2ZFx1ZDU3NFx1ZDU2MCBcdWFjYzRcdWQ2OGRcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMSBcdWJjMTRcdWIyZjdcdWFlMzhcdWM3NDAgXHVjOWMwXHViMDk4XHVhYzAwXHViMjk0IFx1YjM3MCBcdWFjNzhcdWI5YWNcdWIyOTQgXHVjMmRjXHVhYzA0IHQ8c3ViPmk8XC9zdWI+LCBcdWI1Y2ZcdWJhYTlcdWM3NDQgXHVhZTRlXHVjNTQ0XHViMGI0XHViOWFjXHViMjk0IFx1YzgxNVx1YjNjNCBoPHN1Yj5pPFwvc3ViPiAoY20pIFx1Yjk3YyBcdWFjMDBcdWM5YzBcdWFjZTAgXHVjNzg4XHVjNzNjXHViYTcwLCBcdWI5Y2NcdWM1N2RcdWM1ZDAgXHViM2M0XHVjYzI5XHVkNTU4XHVhZTMwIFx1YzgwNFx1YzVkMCBcdWI1Y2ZcdWJhYTlcdWM3NzQgMGNtIFx1Yzc3NFx1ZDU1OFx1Yzc1OCBcdWI0NTBcdWFlZDhcdWI5N2MgXHVhYzAwXHVjOWMwXHVhYzhjIFx1YjQxY1x1YjJlNFx1YmE3NCAtIFx1YjJlY1x1YjlhYyBcdWI5ZDBcdWQ1NzRcdWMxMWMgXHVhY2JkXHViODVjIFx1YzBjMVx1Yzc1OCBoPHN1Yj5pPFwvc3ViPlx1Yzc1OCBcdWQ1NjlcdWM3NzQgSyBcdWM3NzRcdWMwYzFcdWM3NzQgXHViNDFjXHViMmU0XHViYTc0LCBcdWMyMThcdWM2MDFcdWM3NDQgXHViYWJiXHVkNTU4XHViMjk0IFx1YzljMFx1YzZhOVx1Yzc3NFx1Yzc1OCBcdWJhYTlcdWMyMjhcdWM3NDQgXHViY2Y0XHVjN2E1XHVkNTU4XHVjOWMwIFx1YmFiYlx1ZDU2MFx1YzIxOFx1YjNjNCBcdWM3ODhcdWIyZTQoISk8XC9wPlxyXG5cclxuPHA+XHVjOWMwXHVjNmE5XHVjNzc0XHViMjk0IFx1YWMwMFx1YzdhNSBcdWJlNjBcdWI5NzggXHVjMmRjXHVhYzA0IFx1YjBiNFx1YzVkMCBBXHVjNWQwXHVjMTFjIEIgXHVjOWMwXHVjODEwXHVhZTRjXHVjOWMwIFx1YzU0OFx1YzgwNFx1ZDU1OFx1YWM4YyBcdWFjMDBcdWFlMzBcdWI5N2MgXHVjNmQwXHVkNTVjXHViMmU0LiBcdWM5YzBcdWM2YTlcdWM3NzRcdWI5N2MgXHViM2M0XHVjNjQwIFx1YWRmOFx1YjdlY1x1ZDU1YyBcdWFlMzhcdWM3NTggXHVhZTM4XHVjNzc0XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU3NFx1YzhmY1x1Yzc5MC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YzgxNVx1YzIxOCBLLCBOLCBNICgxICZsZTsgSyAmbGU7IDIwMDsgMiAmbGU7IE4gJmxlOyAyMDAwOyAxICZsZTsgTSAmbGU7IDEwMDAwKVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc3NCBcdWQ2YzQgTVx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHVhYzAxIFx1YmMxNFx1YjJmN1x1YWUzOFx1Yzc1OCBcdWM4MTVcdWJjZjRcdWFjMDAgQSwgQiwgdDxzdWI+aTxcL3N1Yj4sIGg8c3ViPmk8XC9zdWI+ICgxICZsZTsgQSwgQiAmbGU7IE47IDEgJmxlOyB0PHN1Yj5pPFwvc3ViPiAmbGU7IDEwPHN1cD41PFwvc3VwPjsgMCAmbGU7IGg8c3ViPmk8XC9zdWI+ICZsZTsgMjAwKSBcdWQ2MTVcdWQwZGNcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzRcdWIyOTQgQVx1YzY0MCBCXHViOTdjIFx1Yzc4N1x1YjI5NCBcdWJjMTRcdWIyZjdcdWFlMzhcdWM3NzQgXHVjODc0XHVjN2FjXHVkNTU4XHViYTcwLCBcdWM3NzQgXHViYzE0XHViMmY3XHVhZTM4XHVjNzQwIHQ8c3ViPmk8XC9zdWI+XHVjNzU4IFx1YzJkY1x1YWMwNFx1Yzc3NCBcdWFjNzhcdWI5YWNcdWJhNzAgaDxzdWI+aTxcL3N1Yj4gXHViOWNjXHVkMDdjIFx1YjVjZlx1YmFhOVx1Yzc0NCBcdWFlNGVcdWM1NDRcdWIwYjRcdWI5YjBcdWIyZTRcdWIyOTQgXHVhYzgzXHVjNzQ0IFx1Yzc1OFx1YmJmOFx1ZDU1Y1x1YjJlNC4gQSAmbmU7IEJcdWM3ODRcdWM3NzQgXHViY2Y0XHVjN2E1XHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI5YzhcdWM5YzBcdWI5YzkgXHVjOTA0XHVjNWQwXHViMjk0IFx1YzJkY1x1Yzc5MVx1YzgxMFx1YWNmYyBcdWIzYzRcdWNjMjlcdWM4MTBcdWM3NzggQSwgQlx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgQSwgQiAmbGU7IE47IEEgJm5lOyBCKTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YzljMFx1YzZhOVx1Yzc3NFx1YWMwMCBcdWM1NDhcdWM4MDRcdWQ1NThcdWFjOGMgQVx1YzVkMFx1YzExYyBCXHVjNWQwXHVjMTFjIFx1ZDU2ZFx1ZDU3NFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0XHViYTc0IFx1YWRmOCBcdWI1NGMgXHVhYzc4XHViOWFjXHViMjk0IFx1YzJkY1x1YWMwNFx1Yzc0NCwgXHVhZGY4XHViN2Y0IFx1YzIxOCBcdWM1YzZcdWIyZTRcdWJhNzQgLTFcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjEwNzc2IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQ29udmV4IEh1bGwiLCJkZXNjcmlwdGlvbiI6IjxwPllvdSBhcmUgdHJhdmVsbGluZyBvbiBhIHNoaXAgaW4gYW4gYXJjaGlwZWxhZ28uIFRoZSBzaGlwIGhhcyBhIGNvbnZleCBodWxsIHdoaWNoIGlzIEsgY2VudGltZXRyZXMgdGhpY2suIFRoZSBhcmNoaXBlbGFnbyBoYXMgTiBpc2xhbmRzLCBudW1iZXJlZCBmcm9tIDEgdG8gTi4gVGhlcmUgYXJlIE0gc2VhIHJvdXRlcyBhbW9uZ3N0IHRoZW0sIHdoZXJlIHRoZSBpdGggcm91dGUgcnVucyBkaXJlY3RseSBiZXR3ZWVuIHR3byBkaWZmZXJlbnQgaXNsYW5kcyBhPHN1Yj5pPFwvc3ViPiBhbmQgYjxzdWI+aTxcL3N1Yj4gKDEgJmxlOyBhPHN1Yj5pPFwvc3ViPiwgYjxzdWI+aTxcL3N1Yj4gJmxlOyBOKSwgdGFrZXMgdDxzdWI+aTxcL3N1Yj4gbWludXRlcyB0byB0cmF2ZWwgYWxvbmcgaW4gZWl0aGVyIGRpcmVjdGlvbiwgYW5kIGhhcyByb2NrcyB0aGF0IHdlYXIgZG93biB0aGUgc2hpcCZyc3F1bztzIGh1bGwgYnkgaDxzdWI+aTxcL3N1Yj4gY2VudGltZXRyZXMuIFRoZXJlIG1heSBiZSBtdWx0aXBsZSByb3V0ZXMgcnVubmluZyBiZXR3ZWVuIGEgcGFpciBvZiBpc2xhbmRzLjxcL3A+XHJcblxyXG48cD5Zb3Ugd291bGQgbGlrZSB0byB0cmF2ZWwgZnJvbSBpc2xhbmQgQSB0byBhIGRpZmZlcmVudCBpc2xhbmQgQiAoMSAmbGU7IEEsIEIgJmxlOyBOKSBhbG9uZyBhIHNlcXVlbmNlIG9mIHNlYSByb3V0ZXMsIHN1Y2ggdGhhdCB5b3VyIHNoaXAmcnNxdW87cyBodWxsIHJlbWFpbnMgaW50YWN0ICZuZGFzaDsgaW4gb3RoZXIgd29yZHMsIHN1Y2ggdGhhdCB0aGUgc3VtIG9mIHRoZSByb3V0ZXMmcnNxdW87IGhpIHZhbHVlcyBpcyBzdHJpY3RseSBsZXNzIHRoYW4gSy48XC9wPlxyXG5cclxuPHA+QWRkaXRpb25hbGx5LCB5b3UgYXJlIGluIGEgaHVycnksIHNvIHlvdSB3b3VsZCBsaWtlIHRvIG1pbmltaXplIHRoZSBhbW91bnQgb2YgdGltZSBuZWNlc3NhcnkgdG8gcmVhY2ggaXNsYW5kIEIgZnJvbSBpc2xhbmQgQS4gSXQgbWF5IG5vdCBiZSBwb3NzaWJsZSB0byByZWFjaCBpc2xhbmQgQiBmcm9tIGlzbGFuZCBBLCBob3dldmVyLCBlaXRoZXIgZHVlIHRvIGluc3VmZmljaWVudCBzZWEgcm91dGVzIG9yIHRoZSBoYXZpbmcgdGhlIHNoaXAmcnNxdW87cyBodWxsIHdlYXIgb3V0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgdGhyZWUgaW50ZWdlcnMgSywgTiBhbmQgTSAoMSAmbGU7IEsgJmxlOyAyMDAsIDIgJmxlOyBOICZsZTsgMjAwMCwgMSAmbGU7IE0gJmxlOyAxMDAwMCksIGVhY2ggc2VwYXJhdGVkIGJ5IG9uZSBzcGFjZS48XC9wPlxyXG5cclxuPHA+VGhlIG5leHQgTSBsaW5lcyBlYWNoIGNvbnRhaW4gNCBpbnRlZ2VycyBhPHN1Yj5pPFwvc3ViPiBiPHN1Yj5pPFwvc3ViPiB0PHN1Yj5pPFwvc3ViPiBhbmQgaDxzdWI+aTxcL3N1Yj4gKDEgJmxlOyBhPHN1Yj5pPFwvc3ViPiwgYjxzdWI+aTxcL3N1Yj4gJmxlOyBOLCAxICZsZTsgdDxzdWI+aTxcL3N1Yj4gJmxlOyAxMDxzdXA+NTxcL3N1cD4sIDAgJmxlOyBoPHN1Yj5pPFwvc3ViPiAmbGU7IDIwMCksIGVhY2ggc2VwYXJhdGVkIGJ5IG9uZSBzcGFjZS4gVGhlIGl0aCBsaW5lIGluIHRoaXMgc2V0IG9mIE0gbGluZXMgZGVzY3JpYmVzIHRoZSBpdGggc2VhIHJvdXRlICh3aGljaCBydW5zIGZyb20gaXNsYW5kIGE8c3ViPmk8XC9zdWI+IHRvIGlzbGFuZCBiPHN1Yj5pPFwvc3ViPiwgdGFrZXMgdDxzdWI+aTxcL3N1Yj4gbWludXRlcyBhbmQgd2VhcnMgZG93biB0aGUgc2hpcCZyc3F1bztzIGh1bGwgYnkgaDxzdWI+aTxcL3N1Yj4gY2VudGltZXRyZXMpLiBOb3RpY2UgdGhhdCBhPHN1Yj5pPFwvc3ViPiAmbmU7IGI8c3ViPmk8XC9zdWI+ICh0aGF0IGlzLCB0aGUgZW5kcyBvZiBhIHNlYSByb3V0ZSBhcmUgZGlzdGluY3QgaXNsYW5kcykuPFwvcD5cclxuXHJcbjxwPlRoZSBsYXN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgdHdvIGludGVnZXJzIEEgYW5kIEIgKDEgJmxlOyBBLCBCICZsZTsgTjsgQSAmbmU7IEIpLCB0aGUgaXNsYW5kcyBiZXR3ZWVuIHdoaWNoIHdlIHdhbnQgdG8gdHJhdmVsLjxcL3A+XHJcblxyXG48cD5Gb3IgMjAlIG9mIG1hcmtzIGZvciB0aGlzIHF1ZXN0aW9uLCBLID0gMSBhbmQgTiAmbGU7IDIwMC4gRm9yIGFub3RoZXIgMjAlIG9mIHRoZSBtYXJrcyBmb3IgdGhpcyBwcm9ibGVtLCBLID0gMSBhbmQgTiAmbGU7IDIwMDAuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T3V0cHV0IGEgc2luZ2xlIGludGVnZXI6IHRoZSBpbnRlZ2VyIHJlcHJlc2VudGluZyB0aGUgbWluaW1hbCB0aW1lIHJlcXVpcmVkIHRvIHRyYXZlbCBmcm9tIEEgdG8gQiB3aXRob3V0IHdlYXJpbmcgb3V0IHRoZSBzaGlwJnJzcXVvO3MgaHVsbCwgb3IgJm1pbnVzOzEgdG8gaW5kaWNhdGUgdGhhdCB0aGVyZSBpcyBubyB3YXkgdG8gdHJhdmVsIGZyb20gQSB0byBCIHdpdGhvdXQgd2VhcmluZyBvdXQgdGhlIHNoaXAmcnNxdW87cyBodWxsLjxcL3A+XHJcbiIsImhpbnQiOiI8cD5FeHBsYW5hdGlvbiBvZiBPdXRwdXQgZm9yIFNhbXBsZSBJbnB1dCAxPFwvcD5cclxuXHJcbjxwPlRoZSBwYXRoIG9mIGxlbmd0aCAxIGZyb20gMSB0byA0IHdvdWxkIHdlYXIgb3V0IHRoZSBodWxsIG9mIHRoZSBzaGlwLiBUaGUgdGhyZWUgcGF0aHMgb2YgbGVuZ3RoIDIgKFsxLCAyLCA0XSBhbmQgWzEsIDMsIDRdIHR3byBkaWZmZXJlbnQgd2F5cykgdGFrZSBhdCBsZWFzdCA4IG1pbnV0ZXMuIFRoZSBwYXRoIFsxLCAyLCAzLCA0XSB0YWtlcyA3IG1pbnV0ZXMgYW5kIG9ubHkgd2VhcnMgZG93biB0aGUgaHVsbCBieSA3IGNlbnRpbWV0cmVzLCB3aGVyZWFzIHRoZSBwYXRoIFsxLCAzLCAyLCA0XSB0YWtlcyAxMyBtaW51dGVzIGFuZCB3ZWFycyBkb3duIHRoZSBodWxsIGJ5IDUgY2VudGltZXRyZXMuPFwvcD5cclxuXHJcbjxwPkV4cGxhbmF0aW9uIG9mIE91dHB1dCBmb3IgU2FtcGxlIElucHV0IDI8XC9wPlxyXG5cclxuPHA+VGhlIGRpcmVjdCBwYXRoIFsxLCAzXSB3ZWFycyBkb3duIHRoZSBodWxsIHRvIDAsIGFzIGRvZXMgdGhlIHBhdGggWzEsIDIsIDNdLjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

Olympiad > Canadian Computing Competition & Olympiad > 2015 > CCC 2015 Senior Division 4번

  • 문제를 번역한 사람: koosaga
  • 데이터를 추가한 사람: palilo