2958번 - 도로 네트워크 다국어

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

문제

도시 N개와 일방통행 도로 M개로 이루어진 도로 네트워크가 있다. 도시는 1번부터 N번까지 번호가 매겨져 있다. 또, 각 도로의 출발 도시와 도착 도시, 그리고 길이를 알고 있다.

도로 E의 도착 도시와 도로 F의 시작 도시가 같다면, 도로 F를 도로 E의 연장선이라고 한다. A에서 B로 가는 경로란 첫 도로의 시작 도시가 A이고 마지막 도로의 도착 도시가 B이면서 각 도로가 이전 도로의 연장선인 도로의 연속이다. 경로의 길이는 경로에 포함된 도로의 길이의 합이다.

A에서 B로 가는 최단 경로는 A에서 B로 가는 경로 중에서 길이가 가장 짧은 것을 말한다.

각각의 도로에 대해서, 그 도로를 포함하는 최단 경로가 몇 개 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 도시의 수 N과 도로의 수 M이 주어진다. (2 ≤ N ≤ 1500, 1 ≤ M ≤ 5000)

다음 M개 줄에는 도로의 정보를 나타내는 세 정수 O, D, L이 주어진다. 도로의 시작 도시가 O이고, 도착 도시가 D이면서 길이가 L인 도로라는 의미이다. O와 D는 다르고, L은  10,000보다 작거나 같은 자연수이다.

출력

총 M개 도로에 대해서 그 도로를 포함하는 최단 경로의 개수를 1,000,000,007로 나눈 나머지를 한 줄에 하나씩 출력한다. 출력은 입력으로 주어진 도로 순서대로 해야 한다.

예제 입력 1 

4 3
1 2 5
2 3 5
3 4 5

예제 출력 1 

3
4
3

예제 입력 2 

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

예제 출력 2 

2
3
2
1

예제 입력 3 

5 8
1 2 20
1 3 2
2 3 2
4 2 3
4 2 3
3 4 5
4 3 5
5 4 20

예제 출력 3 

0
4
6
6
6
7
2
6
W3sicHJvYmxlbV9pZCI6IjI5NTgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIzYzRcdWI4NWMgXHViMTI0XHVkMmI4XHVjNmNjXHVkMDZjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWIzYzRcdWMyZGMgTlx1YWMxY1x1YzY0MCBcdWM3N2NcdWJjMjlcdWQxYjVcdWQ1ODkgXHViM2M0XHViODVjIE1cdWFjMWNcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1YjNjNFx1Yjg1YyBcdWIxMjRcdWQyYjhcdWM2Y2NcdWQwNmNcdWFjMDAgXHVjNzg4XHViMmU0LiBcdWIzYzRcdWMyZGNcdWIyOTQgMVx1YmM4OFx1YmQ4MFx1ZDEzMCBOXHViYzg4XHVhZTRjXHVjOWMwIFx1YmM4OFx1ZDYzOFx1YWMwMCBcdWI5ZTRcdWFjYThcdWM4MzggXHVjNzg4XHViMmU0LiBcdWI2MTAsIFx1YWMwMSBcdWIzYzRcdWI4NWNcdWM3NTggXHVjZDljXHViYzFjIFx1YjNjNFx1YzJkY1x1YzY0MCBcdWIzYzRcdWNjMjkgXHViM2M0XHVjMmRjLCBcdWFkZjhcdWI5YWNcdWFjZTAgXHVhZTM4XHVjNzc0XHViOTdjIFx1YzU0Y1x1YWNlMCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjNjNFx1Yjg1YyBFXHVjNzU4IFx1YjNjNFx1Y2MyOSBcdWIzYzRcdWMyZGNcdWM2NDAgXHViM2M0XHViODVjIEZcdWM3NTggXHVjMmRjXHVjNzkxIFx1YjNjNFx1YzJkY1x1YWMwMCBcdWFjMTlcdWIyZTRcdWJhNzQsIFx1YjNjNFx1Yjg1YyBGXHViOTdjIFx1YjNjNFx1Yjg1YyBFXHVjNzU4IFx1YzVmMFx1YzdhNVx1YzEyMFx1Yzc3NFx1Yjc3Y1x1YWNlMCBcdWQ1NWNcdWIyZTQuIEFcdWM1ZDBcdWMxMWMgQlx1Yjg1YyBcdWFjMDBcdWIyOTQgXHVhY2JkXHViODVjXHViNzgwIFx1Y2NhYiBcdWIzYzRcdWI4NWNcdWM3NTggXHVjMmRjXHVjNzkxIFx1YjNjNFx1YzJkY1x1YWMwMCBBXHVjNzc0XHVhY2UwIFx1YjljOFx1YzljMFx1YjljOSBcdWIzYzRcdWI4NWNcdWM3NTggXHViM2M0XHVjYzI5IFx1YjNjNFx1YzJkY1x1YWMwMCBCXHVjNzc0XHViYTc0XHVjMTFjIFx1YWMwMSBcdWIzYzRcdWI4NWNcdWFjMDAgXHVjNzc0XHVjODA0IFx1YjNjNFx1Yjg1Y1x1Yzc1OCBcdWM1ZjBcdWM3YTVcdWMxMjBcdWM3NzggXHViM2M0XHViODVjXHVjNzU4IFx1YzVmMFx1YzE4ZFx1Yzc3NFx1YjJlNC4gXHVhY2JkXHViODVjXHVjNzU4IFx1YWUzOFx1Yzc3NFx1YjI5NCBcdWFjYmRcdWI4NWNcdWM1ZDAgXHVkM2VjXHVkNTY4XHViNDFjIFx1YjNjNFx1Yjg1Y1x1Yzc1OCBcdWFlMzhcdWM3NzRcdWM3NTggXHVkNTY5XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5BXHVjNWQwXHVjMTFjIEJcdWI4NWMgXHVhYzAwXHViMjk0IFx1Y2Q1Y1x1YjJlOCBcdWFjYmRcdWI4NWNcdWIyOTQgQVx1YzVkMFx1YzExYyBCXHViODVjIFx1YWMwMFx1YjI5NCBcdWFjYmRcdWI4NWMgXHVjOTExXHVjNWQwXHVjMTFjIFx1YWUzOFx1Yzc3NFx1YWMwMCBcdWFjMDBcdWM3YTUgXHVjOWU3XHVjNzQwIFx1YWM4M1x1Yzc0NCBcdWI5ZDBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMVx1YWMwMVx1Yzc1OCBcdWIzYzRcdWI4NWNcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjLCBcdWFkZjggXHViM2M0XHViODVjXHViOTdjIFx1ZDNlY1x1ZDU2OFx1ZDU1OFx1YjI5NCBcdWNkNWNcdWIyZTggXHVhY2JkXHViODVjXHVhYzAwIFx1YmE4NyBcdWFjMWMgXHVjNzg4XHViMjk0XHVjOWMwIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWIzYzRcdWMyZGNcdWM3NTggXHVjMjE4IE5cdWFjZmMgXHViM2M0XHViODVjXHVjNzU4IFx1YzIxOCBNXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDImbmJzcDsmbGU7IE4gJmxlOyAxNTAwLCAxICZsZTsgTSAmbGU7IDUwMDApPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBNXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWIzYzRcdWI4NWNcdWM3NTggXHVjODE1XHViY2Y0XHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCBcdWMxMzggXHVjODE1XHVjMjE4IE8sIEQsIExcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWIzYzRcdWI4NWNcdWM3NTggXHVjMmRjXHVjNzkxIFx1YjNjNFx1YzJkY1x1YWMwMCBPXHVjNzc0XHVhY2UwLCBcdWIzYzRcdWNjMjkgXHViM2M0XHVjMmRjXHVhYzAwIERcdWM3NzRcdWJhNzRcdWMxMWMgXHVhZTM4XHVjNzc0XHVhYzAwIExcdWM3NzggXHViM2M0XHViODVjXHViNzdjXHViMjk0IFx1Yzc1OFx1YmJmOFx1Yzc3NFx1YjJlNC4gT1x1YzY0MCBEXHViMjk0IFx1YjJlNFx1Yjk3NFx1YWNlMCwgTFx1Yzc0MCZuYnNwOyAxMCwwMDBcdWJjZjRcdWIyZTQgXHVjNzkxXHVhYzcwXHViMDk4IFx1YWMxOVx1Yzc0MCBcdWM3OTBcdWM1ZjBcdWMyMThcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjZDFkIE1cdWFjMWMgXHViM2M0XHViODVjXHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYyBcdWFkZjggXHViM2M0XHViODVjXHViOTdjIFx1ZDNlY1x1ZDU2OFx1ZDU1OFx1YjI5NCBcdWNkNWNcdWIyZTggXHVhY2JkXHViODVjXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyAxLDAwMCwwMDAsMDA3XHViODVjIFx1YjA5OFx1YjIwOCBcdWIwOThcdWJhMzhcdWM5YzBcdWI5N2MgXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWQ1NThcdWIwOThcdWM1MjkgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWNkOWNcdWI4MjVcdWM3NDAgXHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljNCBcdWIzYzRcdWI4NWMgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMjk1OCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6Ik5BSktSQUNJIiwiZGVzY3JpcHRpb24iOiI8cD5BIHJvYWQgbmV0d29yayBpbiBhIGNvdW50cnkgY29uc2lzdHMgb2YgTiBjaXRpZXMgYW5kIE0gb25lLXdheSByb2Fkcy4gVGhlIGNpdGllcyBhcmUgbnVtYmVyZWQgMSB0aHJvdWdoIE4uIEZvciBlYWNoIHJvYWQgd2Uga25vdyB0aGUgb3JpZ2luIGFuZCBkZXN0aW5hdGlvbiBjaXRpZXMsIGFzIHdlbGwgYXMgaXRzIGxlbmd0aC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+V2Ugc2F5IHRoYXQgdGhlIHJvYWQgRiBpcyBhIGNvbnRpbnVhdGlvbiBvZiByb2FkIEUgaWYgdGhlIGRlc3RpbmF0aW9uIGNpdHkgb2Ygcm9hZCBFIGlzIHRoZSBzYW1lIGFzIHRoZSBvcmlnaW4gY2l0eSBvZiByb2FkIEYuIEEgcGF0aCBmcm9tIGNpdHkgQSB0byBjaXR5IEIgaXMgYSBzZXF1ZW5jZSBvZiByb2FkIHN1Y2ggdGhhdCBvcmlnaW4gb2YgdGhlIGZpcnN0IHJvYWQgaXMgY2l0eSBBLCBlYWNoIG90aGVyIHJvYWQgaXMgYSBjb250aW51YXRpb24gb2YgdGhlIG9uZSBiZWZvcmUgaXQsIGFuZCB0aGUgZGVzdGluYXRpb24gb2YgdGhlIGxhc3Qgcm9hZCBpcyBjaXR5IEIuIFRoZSBsZW5ndGggb2YgdGhlIHBhdGggaXMgdGhlIHN1bSBvZiBsZW5ndGhzIG9mIGFsbCByb2FkcyBpbiBpdC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+QSBwYXRoIGZyb20gQSB0byBCIGlzIGEgc2hvcnRlc3QgcGF0aCBpZiB0aGVyZSBpcyBubyBvdGhlciBwYXRoIGZyb20gQSB0byBCIHRoYXQgaXMgc2hvcnRlciBpbiBsZW5ndGguJm5ic3A7PFwvcD5cclxuXHJcbjxwPllvdXIgdGFzayBpcyB0bywgZm9yIGVhY2ggcm9hZCwgb3V0cHV0IGhvdyBtYW55IGRpZmZlcmVudCBzaG9ydGVzdCBwYXRocyBjb250YWluaW5nIHRoYXQgcm9hZCwgbW9kdWxvIDEgMDAwIDAwMCAwMDcuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBjb250YWlucyB0d28gaW50ZWdlcnMgTiBhbmQgTSAoMSAmbGU7IE4gJmxlOyAxNTAwLCAxICZsZTsgTSAmbGU7IDUwMDApLCB0aGUgbnVtYmVyIG9mIGNpdGllcyBhbmQgcm9hZHMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkVhY2ggb2YgdGhlIGZvbGxvd2luZyBNIGxpbmVzIGNvbnRhaW5zIHRocmVlIHBvc2l0aXZlIGludGVnZXJzIE8sIEQgYW5kIEwuIFRoZXNlIHJlcHJlc2VudCBhIG9uZS13YXkgcm9hZCBmcm9tIGNpdHkgTyB0byBjaXR5IEQgb2YgbGVuZ3RoIEwuIFRoZSBudW1iZXJzIE8gYW5kIEQgd2lsbCBiZSBkaWZmZXJlbnQgYW5kIEwgd2lsbCBiZSBhdCBtb3N0IDEwMDAwLiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk91dHB1dCBNIGludGVnZXJzIGVhY2ggb24gaXRzIG93biBsaW5lICZuZGFzaDsgZm9yIGVhY2ggcm9hZCwgdGhlIG51bWJlciBvZiBkaWZmZXJlbnQgc2hvcnRlc3QgcGF0aHMgY29udGFpbmluZyBpdCwgbW9kdWxvIDEgMDAwIDAwMCAwMDcuIFRoZSBvcmRlciBvZiB0aGVzZSBudW1iZXJzIHNob3VsZCBtYXRjaCB0aGUgb3JkZXIgb2Ygcm9hZHMgaW4gdGhlIGlucHV0LiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

Contest > Croatian Open Competition in Informatics > COCI 2008/2009 > Contest #3 6번

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO

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

한국어 | English (Beta)