Shortest path queries
All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
With the impressive achievement in competitive programming Jem was offered an internship at IBER - a tech company that provides an alternative to tradditional taxi service.
Jem first task was help IBER quickly calculate the distance between two arbitrary locations in Jem's city. As an experienced competitive programmer Jem understand that this is not a trivial problem with general graph. Fortunately after investigate the city map Jem found out that the roads system is have a special form which may make Jem's problem easier to deal with.
There are N locations in the city and M bidirectional road connecting them. Each road i have the length of Ci and no two road connect the same pair of locations. The roads system is designed in a way that from a specific location one can travel to any other locations. The most important point is that there is no location belong to more than one cycle in the graph corresponding to road network.
So Jem already got his solution. If you want to secure an internship at IBER maybe you can try to solve this problem too!
- The first line of the input contains two number N and M
- In the next M line each line contains three numbers u, v and c represent a road of length c connects location u and v.
- Next line contains a single number Q represents the number of queries.
- In the next Q lines each line contains two numbers u and v corresponding to a query of the length of the shortest path between location u and v.
For each query print out the corresponding result in one line.
- 2 ≤ N ≤ 105
- 1 ≤ M ≤ 2 × 105
- 1 ≤ Q ≤ 105
- 1 ≤ c ≤ 104
Input 1: 4 3 1 2 2 2 3 3 2 4 4 2 1 4 4 3 Output 1: 6 7 Input 2: 7 8 1 2 2 1 3 4 2 3 1 3 4 1 4 5 1 4 7 1 5 6 2 6 7 1 3 1 4 5 7 1 6 Output 2: 4 2 6
Test 2: the graph is shown in the picture below.
The shortest path for each query are:
- From 1 to 4: 1 -> 2 -> 3 -> 4
- From 5 to 7: 5 -> 4 -> 7
- From 1 to 6: 1 -> 2 -> 3 -> 4 -> 7 -> 6
|Tags||cook74, dynamic-programming, graph, hard, tuananh93|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 6.3, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYPY, PYTH, PYTH 3.5, RUBY, SCALA, SCM chicken, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC|
Fetching successful submissions
If you are still having problems, see a sample solution here.