시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB246835433.750%

문제

맨체스터에 있는 도로는 모두 일방 통행이다. 또한 이 도로는 모두 1시간에 지나갈 수 있는 차의 개수 제한이 있다. 길(경로)에도 차의 개수 제한이 있는데, 이것은 이 길에 있는 도로의 제한 중 최솟값이다.

A에서 B로 가는 중복 비율은 A에서 B로 가는 모든 길을 동시에 이용했을 때 1시간 동안 B에 도착할 수 있는 차의 최대 개수와 길 1개를 이용했을 때 도착할 수 있는 최대 개수의 비율이다.

최소 중복 비율은 길 1개를 이용했을 때 도착할 수 있는 최대 개수가 가장 큰 값이 된다.

맨체스터의 도로 정보와 A, B가 주어졌을 때, 최소 중복 비율을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T (1 ≤ T ≤ 1,000)가 주어진다. 각 테스트 케이스는 다음과 같이 구성되어 있다.

첫째 줄에 정수 4개가 주어진다. 차례대로 N, E, A, B이다. N (2 ≤ N ≤ 1,000)은 그래프의 정점의 개수, E (E ≥ 1)는 간선의 개수이다. A (0 ≤ A < N)와 B (0 ≤ B < N, A ≠ B)는 문제 설명에 나와있는 A와 B이다.

그 다음 E개 줄은 각 간선에 대한 정보이다. 이 정보는 U V W로 구성되어 있는데, U (0 ≤ U < N)와 V (0 ≤ V < N, V ≠ U)는 그래프의 정점이고, W (1 ≤ W ≤ 1000)는 U에서 V로 향하는 도로의 1시간에 지나갈 수 있는 차의 개수 제한이다.

출력

각 테스트 케이스에 대해 최소 중복 비율을 소수점 셋째자리까지 출력한다. 

예제 입력 1

1
7 11 0 6
0 1 3
0 3 3
1 2 4
2 0 3
2 3 1
2 4 2
3 4 2
3 5 6
4 1 1
4 6 1
5 6 9

예제 출력 1

1.667
W3sicHJvYmxlbV9pZCI6IjI2NzkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWI5ZThcdWNjYjRcdWMyYTRcdWQxMzBcdWM3NTggXHViM2M0XHViODVjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWI5ZThcdWNjYjRcdWMyYTRcdWQxMzBcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YjNjNFx1Yjg1Y1x1YjI5NCBcdWJhYThcdWI0NTAgXHVjNzdjXHViYzI5IFx1ZDFiNVx1ZDU4OVx1Yzc3NFx1YjJlNC4gXHViNjEwXHVkNTVjIFx1Yzc3NCBcdWIzYzRcdWI4NWNcdWIyOTQgXHViYWE4XHViNDUwIDFcdWMyZGNcdWFjMDRcdWM1ZDAgXHVjOWMwXHViMDk4XHVhYzA4IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjYzI4XHVjNzU4IFx1YWMxY1x1YzIxOCBcdWM4MWNcdWQ1NWNcdWM3NzQgXHVjNzg4XHViMmU0LiBcdWFlMzgoXHVhY2JkXHViODVjKVx1YzVkMFx1YjNjNCBcdWNjMjhcdWM3NTggXHVhYzFjXHVjMjE4IFx1YzgxY1x1ZDU1Y1x1Yzc3NCBcdWM3ODhcdWIyOTRcdWIzNzAsIFx1Yzc3NFx1YWM4M1x1Yzc0MCBcdWM3NzQgXHVhZTM4XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWIzYzRcdWI4NWNcdWM3NTggXHVjODFjXHVkNTVjIFx1YzkxMSBcdWNkNWNcdWMxOWZcdWFjMTJcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPkFcdWM1ZDBcdWMxMWMgQlx1Yjg1YyBcdWFjMDBcdWIyOTQgXHVjOTExXHViY2Y1IFx1YmU0NFx1YzcyOFx1Yzc0MCBBXHVjNWQwXHVjMTFjIEJcdWI4NWMgXHVhYzAwXHViMjk0IFx1YmFhOFx1YjRlMCBcdWFlMzhcdWM3NDQgXHViM2Q5XHVjMmRjXHVjNWQwIFx1Yzc3NFx1YzZhOVx1ZDU4OFx1Yzc0NCBcdWI1NGMgMVx1YzJkY1x1YWMwNCBcdWIzZDlcdWM1NDggQlx1YzVkMCBcdWIzYzRcdWNjMjlcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWNjMjhcdWM3NTggXHVjZDVjXHViMzAwIFx1YWMxY1x1YzIxOFx1YzY0MCBcdWFlMzggMVx1YWMxY1x1Yjk3YyBcdWM3NzRcdWM2YTlcdWQ1ODhcdWM3NDQgXHViNTRjIFx1YjNjNFx1Y2MyOVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1Y2Q1Y1x1YjMwMCBcdWFjMWNcdWMyMThcdWM3NTggXHViZTQ0XHVjNzI4XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWNkNWNcdWMxOGMgXHVjOTExXHViY2Y1IFx1YmU0NFx1YzcyOFx1Yzc0MCBcdWFlMzggMVx1YWMxY1x1Yjk3YyBcdWM3NzRcdWM2YTlcdWQ1ODhcdWM3NDQgXHViNTRjIFx1YjNjNFx1Y2MyOVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1Y2Q1Y1x1YjMwMCBcdWFjMWNcdWMyMThcdWFjMDAgXHVhYzAwXHVjN2E1IFx1ZDA3MCBcdWFjMTJcdWM3NzQgXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI5ZThcdWNjYjRcdWMyYTRcdWQxMzBcdWM3NTggXHViM2M0XHViODVjIFx1YzgxNVx1YmNmNFx1YzY0MCBBLCBCXHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1Y2Q1Y1x1YzE4YyBcdWM5MTFcdWJjZjUgXHViZTQ0XHVjNzI4XHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWMxY1x1YzIxOCBUICgxICZsZTsgVCAmbGU7IDEsMDAwKVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NzQgXHVhZDZjXHVjMTMxXHViNDE4XHVjNWI0IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWM4MTVcdWMyMTggNFx1YWMxY1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Y2MyOFx1Yjg0MFx1YjMwMFx1Yjg1YyBOLCBFLCBBLCBCXHVjNzc0XHViMmU0LiBOICgyICZsZTsgTiAmbGU7IDEsMDAwKVx1Yzc0MCBcdWFkZjhcdWI3OThcdWQ1MDRcdWM3NTggXHVjODE1XHVjODEwXHVjNzU4IFx1YWMxY1x1YzIxOCwgRSAoRSAmZ2U7IDEpXHViMjk0IFx1YWMwNFx1YzEyMFx1Yzc1OCBcdWFjMWNcdWMyMThcdWM3NzRcdWIyZTQuIEEgKDAgJmxlOyBBICZsdDsgTilcdWM2NDAgQiAoMCAmbGU7IEIgJmx0OyBOLCBBICZuZTsgQilcdWIyOTQgXHViYjM4XHVjODFjIFx1YzEyNFx1YmE4NVx1YzVkMCBcdWIwOThcdWM2NDBcdWM3ODhcdWIyOTQgQVx1YzY0MCBCXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFkZjggXHViMmU0XHVjNzRjIEVcdWFjMWMgXHVjOTA0XHVjNzQwIFx1YWMwMSBcdWFjMDRcdWMxMjBcdWM1ZDAgXHViMzAwXHVkNTVjIFx1YzgxNVx1YmNmNFx1Yzc3NFx1YjJlNC4gXHVjNzc0IFx1YzgxNVx1YmNmNFx1YjI5NCBVIFYgV1x1Yjg1YyBcdWFkNmNcdWMxMzFcdWI0MThcdWM1YjQgXHVjNzg4XHViMjk0XHViMzcwLCBVICgwICZsZTsgVSAmbHQ7IE4pXHVjNjQwIFYgKDAgJmxlOyBWICZsdDsgTiwgViAmbmU7IFUpXHViMjk0IFx1YWRmOFx1Yjc5OFx1ZDUwNFx1Yzc1OCBcdWM4MTVcdWM4MTBcdWM3NzRcdWFjZTAsIFcgKDEgJmxlOyBXICZsZTsgMTAwMClcdWIyOTQgVVx1YzVkMFx1YzExYyBWXHViODVjIFx1ZDVhNVx1ZDU1OFx1YjI5NCBcdWIzYzRcdWI4NWNcdWM3NTggMVx1YzJkY1x1YWMwNFx1YzVkMCBcdWM5YzBcdWIwOThcdWFjMDggXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWNjMjhcdWM3NTggXHVhYzFjXHVjMjE4IFx1YzgxY1x1ZDU1Y1x1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzQgXHVjZDVjXHVjMThjIFx1YzkxMVx1YmNmNSBcdWJlNDRcdWM3MjhcdWM3NDQgXHVjMThjXHVjMjE4XHVjODEwIFx1YzE0Ylx1YzlmOFx1Yzc5MFx1YjlhY1x1YWU0Y1x1YzljMCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMjY3OSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlJvdXRlIFJlZHVuZGFuY3kiLCJkZXNjcmlwdGlvbiI6IjxwPkEgY2l0eSBpcyBtYWRlIHVwIGV4Y2x1c2l2ZWx5IG9mIG9uZS13YXkgc3RyZWV0cy4gRWFjaCBzdHJlZXQgaW4gdGhlIGNpdHkgaGFzIGEgY2FwYWNpdHksIHRoZSBtYXhpbXVtIG51bWJlciBvZiBjYXJzIGl0IGNhbiBjYXJyeSBwZXIgaG91ci4gQW55IHJvdXRlIChwYXRoKSBhbHNvIGhhcyBhIGNhcGFjaXR5LCB3aGljaCBpcyB0aGUgbWluaW11bSBvZiB0aGUgY2FwYWNpdGllcyBvZiB0aGUgc3RyZWV0cyBhbG9uZyB0aGF0IHJvdXRlLjxcL3A+XHJcblxyXG48cD5UaGUgcmVkdW5kYW5jeSByYXRpbyBmcm9tIHBvaW50IEEgdG8gcG9pbnQgQiBpcyB0aGUgcmF0aW8gb2YgdGhlIG1heGltdW0gbnVtYmVyIG9mIGNhcnMgdGhhdCBjYW4gZ2V0IGZyb20gQSB0byBCIGluIGFuIGhvdXIgdXNpbmcgYWxsIHJvdXRlcyBzaW11bHRhbmVvdXNseSwgdG8gdGhlIG1heGltdW0gbnVtYmVyIG9mIGNhcnMgdGhhdCBjYW4gZ2V0IGZyb20gQSB0byBCIGluIGFuIGhvdXIgdXNpbmcganVzdCBvbmUgcm91dGUuIFRoZSBtaW5pbXVtIHJlZHVuZGFuY3kgcmF0aW8gaXMgdGhlIG51bWJlciBvZiBjYXJzIHRoYXQgY2FuIGdldCBmcm9tIEEgdG8gQiBpbiBhbiBob3VyIHVzaW5nIGFsbCBwb3NzaWJsZSByb3V0ZXMgc2ltdWx0YW5lb3VzbHksIGRpdmlkZWQgYnkgdGhlIGNhcGFjaXR5IG9mIHRoZSBzaW5nbGUgcm91dGUgd2l0aCB0aGUgbGFyZ2VzdCBjYXBhY2l0eS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIGEgc2luZ2xlIGludGVnZXIgUCwgKDEgJmxlOyBQICZsZTsgMTAwMCksIHdoaWNoIGlzIHRoZSBudW1iZXIgb2YgZGF0YSBzZXRzIHRoYXQgZm9sbG93LiBFYWNoIGRhdGEgc2V0IGNvbnNpc3RzIG9mIHNldmVyYWwgbGluZXMgYW5kIHJlcHJlc2VudHMgYSBkaXJlY3RlZCBncmFwaCB3aXRoIHBvc2l0aXZlIGludGVnZXIgd2VpZ2h0cy48XC9wPlxyXG5cclxuPHA+VGhlIGZpcnN0IGxpbmUgb2YgZWFjaCBkYXRhIHNldCBjb250YWlucyBmaXZlIHNwYWNlIHNlcGFyYXRlZCBpbnRlZ2Vycy4gVGhlIGZpcnN0IGludGVnZXIsIEQgaXMgdGhlIGRhdGEgc2V0IG51bWJlci4gVGhlIHNlY29uZCBpbnRlZ2VyLCBOICgyICZsZTsgTiAmbGU7IDEwMDApLCBpcyB0aGUgbnVtYmVyIG9mIG5vZGVzIGluIHRoZSBncmFwaC4gVGhlIHRoaXJkIGludGVnZXIsIEUsIChFICZnZTsgMSksIGlzIHRoZSBudW1iZXIgb2YgZWRnZXMgaW4gdGhlIGdyYXBoLiBUaGUgZm91cnRoIGludGVnZXIsIEEsICgwICZsZTsgQSAmbHQ7IE4pLCBpcyB0aGUgaW5kZXggb2YgcG9pbnQgQS4gVGhlIGZpZnRoIGludGVnZXIsIEIsICgwICZsZTsgQiAmbHQ7IE4sIEEgJm5lOyBCKSwgaXMgdGhlIGluZGV4IG9mIHBvaW50IEIuPFwvcD5cclxuXHJcbjxwPlRoZSByZW1haW5pbmcgRSBsaW5lcyBkZXNjcmliZSBlYWNoIGVkZ2UuIEVhY2ggbGluZSBjb250YWlucyB0aHJlZSBzcGFjZSBzZXBhcmF0ZWQgaW50ZWdlcnMuIFRoZSBmaXJzdCBpbnRlZ2VyLCBVICgwICZsZTsgVSAmbHQ7IE4pLCBpcyB0aGUgaW5kZXggb2Ygbm9kZSBVLiBUaGUgc2Vjb25kIGludGVnZXIsIFYgKDAgJmxlOyBWICZsdDsgTiwgViAmbmU7IFUpLCBpcyB0aGUgaW5kZXggb2Ygbm9kZSBWLiBUaGUgdGhpcmQgaW50ZWdlciwgVyAoMSAmbGU7IFcgJmxlOyAxMDAwKSwgaXMgdGhlIGNhcGFjaXR5ICh3ZWlnaHQpIG9mIHRoZSBwYXRoIGZyb20gVSB0byBWLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIGRhdGEgc2V0IHRoZXJlIGlzIG9uZSBsaW5lIG9mIG91dHB1dC4gSXQgY29udGFpbnMgdGhlIGRhdGEgc2V0IG51bWJlciAoTikgZm9sbG93ZWQgYnkgYSBzaW5nbGUgc3BhY2UsIGZvbGxvd2VkIGJ5IGEgZmxvYXRpbmctcG9pbnQgdmFsdWUgd2hpY2ggaXMgdGhlIG1pbmltdW0gcmVkdW5kYW5jeSByYXRpbyB0byAzIGRpZ2l0cyBhZnRlciB0aGUgZGVjaW1hbCBwb2ludC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

ICPC > Regionals > North America > Greater New York Region > 2011 Greater New York Programming Contest E번

  • 문제를 번역한 사람: baekjoon
  • 데이터를 추가한 사람: sedev57