Ciel and Tomya
All submissions for this problem are available.
Tomya is a girl. She loves Chef Ciel very much.
Today, too, Tomya is going to Ciel's restaurant.
Of course, Tomya would like to go to Ciel's restaurant as soon as possible.
Therefore Tomya uses one of the shortest paths from Tomya's house to Ciel's restaurant.
On the other hand, Tomya is boring now to use the same path many times.
So Tomya wants to know the number of shortest paths from Tomya's house to Ciel's restaurant.
Your task is to calculate the number under the following assumptions.
This town has N intersections and M two way roads.
The i-th road connects from the Ai-th intersection to the Bi-th intersection, and its length is
Tomya's house is in the 1st intersection, and Ciel's restaurant is in the N-th intersection.
The first line contains an integer T, the number of test cases.
Then T test cases follow.
The first line of each test case contains 2 integers N, M.
Then next M lines contains 3 integers denoting Ai, Bi and Ci.
For each test case, print the number of shortest paths from Tomya's house to Ciel's restaurant.
1 ≤ T ≤ 10
2 ≤ N ≤ 10
1 ≤ M ≤ N ∙ (N – 1) / 2
1 ≤ Ai, Bi ≤ N
1 ≤ Ci ≤ 10
Ai ≠ Bi
If i ≠ j and Ai = Aj, then Bi ≠ Bj
There is at least one path from Tomya's house to Ciel's restaurant.
2 3 3 1 2 3 2 3 6 1 3 7 3 3 1 2 3 2 3 6 1 3 9
In the first sample, only one shortest path exists, which is 1-3.
In the second sample, both paths 1-2-3 and 1-3 are the shortest paths.
|Tags||backtracking, cook24, laycurse, simple|
|Time Limit:||0.395522 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.