Problem hidden
This problem was hidden by Editorial Board member probably because it has incorrect language version or invalid test data, or description of the problem is not clear.
Submit All submissions Best solutions PDF Back to list

MANG2 - Mạng máy tính 2

Hoàng là giám đốc công ty xây dựng. Anh đang xây dựng một mạng lưới các cầu nối các bản làng ở vùng núi. Có tất cả N bản làng và M cây cầu chỉ có một chiều. Các bản làng được đánh số từ 1 tới N.

Với mỗi cầu, Hoàng sẽ biết điểm đầu và điểm cuối cần xây dựng và chiều dài cần xây dựng của chiếc cầu. Ta nói rằng cây cầu F là cầu liên tục của cầu E nếu bản làng cuối của cầu E sẽ là bản làng đầu của cây cầu F. Một đường đi từ bản làng A tới bản làng B là một dãy các cây cầu thỏa mãn cây cầu đầu tiên có điểm đầu là bản lảng A, mỗi cây cầu tiếp theo được nối vào sẽ thỏa mãn là cầu liên tục của cầu trước đó, và cây cầu cuối cùng có điểm cuối là bản làng B.

Chiều dài của đường đi là tổng chiều dài của các cây cầu Một đường đi từ A đến B gọi là đường đi ngắn nhất nếu không có con đường khác từ A đến B ngắn hơn chiều dài của nó Nhiệm vụ của bạn là với mỗi cây cầu đã cho trong Input, có bao nhiêu đường đi ngắn nhất khác nhau chứa đựng cây cầu đó, kết quả chia lấy dư cho 109+7 Input Dòng đầu tiên gồm 2 số nguyên N và M (1<=N<=1500, 1<=M<=5000), số lượng các bản làng và cây cầu Mỗi dòng trong số M dòng tiếp theo gồm 3 số nguyên dương O, D và L. Những số này biểu diễn một cây cầu một chiều từ thành phố O tới thành phố D và có chiều dài là L.

Các số O và D sẽ phân biệt và L tối đa là 10000.

Ouput Đưa ra M số nguyên trên mỗi dòng, với mỗi cây cầu, đưa ra số đường đi ngắn nhất khác nhau chứa đựng cây cầu đó, kết quả chia lấy dư cho 109+7.

Ví dụ:

Input Output
4 3 
1 2 5 
2 3 5 
3 4 5

3

4

3

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

2

3

2

1

 
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 		 0 
4 
6 
6 
6 
7 
2 
6 

Giải thích: Trong test số 1, ứng với Input 1 2 5 có 3 đường đi ngắn nhất và khác nhau đi qua cây cầu nối bản làng 1 với bản làng 2, đó là đường đi ngắn nhất nối đỉnh 1 với đỉnh 2 (1->2), đường đi ngắn nhất nối đỉnh 1 với đỉnh 3 (1->2->3), và đường đi ngắn nhất nối đỉnh 1 với đỉnh 4 (1->2->3->4). Do vậy câu trả lời của Input 1 2 5 sẽ là 3

Trong test số 1, với Input 2 3 5  có 4 đường đi ngắn nhất và khác nhau đi qua cây cầu nối bản làng 2 với bản làng 3, đường đi ngắn nhất nối đỉnh 1 với đỉnh 3 (1->2->3), và đường đi ngắn nhất nối đỉnh 1 với đỉnh 4 (1->2->3->4), đường đi ngắn nhất nối đỉnh 2 với đỉnh 3 (2->3) và đường đi ngắn nhất nối đỉnh 2 với đỉnh 4 (2->3->4). Do vậy câu trả lời của Input 2 3 5 sẽ là 4

Trong test số 1, với Input 3 4 3  có 3 đường đi ngắn nhất và khác nhau đi qua cây cầu nối bản làng 3 với bản làng 4,đó là đường đi ngắn nhất nối đỉnh 1 với đỉnh 4 (1->2->3->4),đường đi ngắn nhất nối đỉnh 2 với đỉnh 4 (2->3->4), và đường đi ngắn nhất nối đỉnh 3 với đỉnh 4 (3->4). Do vậy câu trả lời của Input 3 4 5 sẽ là 4

Submit solution!
Added by:trungkien
Date:2018-08-22
Time limit:1s-5s
Source limit:500000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: DART ELIXIR ERL JS-RHINO JS-MONKEY KTLN LUA NEM NICE NIM NODEJS OBJC OBJC-CLANG OCAML OCT PERL PERL6 PHP PICO PIKE PRLG-swi PROLOG PY_NBC R RACKET RUBY RUST SCALA SCM guile SCM qobi CHICKEN SED ST SQLITE SWIFT TCL UNLAMBDA VB.NET WHITESPACE
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.