NINJA6 - TRAVELLING DILEMMA

A graph of a country is given. There are N cities and M number of roads. Each road connects two cities. Now you are given two modes of traveling from one city to another.

  • By using public transportation.
  • By using your own car. (Which you can use only once between any two cities on your way). You may or may not use this mode of travel.

The country's map is given as a graph with N nodes (labeled from 1 to N), and the initial station is node S and the destination is node D. There are two undirected edges between each of the given nodes:

  • one denotes the cost of a path using public transportation, r.
  • and the other denotes the cost of a path using your own car, t.

Now you have to find the most optimal way (in terms of time of cost) from S to D with or without using your entitled car ride. Output the minimized cost of your travel from the source to the destination.

Input:

The first line contains T, the number of test cases.

For each test case:

The first line contains two space-separated integers, N (the number of cities in the map) and M (the number of roads in the map), respectively.

The next M lines each have four space separated integers c1, c2, r, and t, respectively; c1 and c2 denote two cities connected by a road, r is the cost for using the public transportation, and t is the cost of taking your own car on the road.

The last line has two space-separated integers, S (Starting city) and D (Destination), respectively.

Output:

For each test case, print a single line with minimum travel cost. If the destination (D) is unreachable from the source node (S), print −1.

Constraints:

1 ≤ T ≤ 10

2 ≤ N ≤ 3000

1 ≤ M ≤ N×(N−1)

1 ≤ x, y, S, D ≤ N

1 ≤ r, t ≤ 500

Sample:

Input:
1
4 5
1 2 6 5
1 3 4 5
2 3 6 1
2 4 3 4
3 4 5 7
1 4

Output:
8

Added by:mombassa
Date:2016-02-17
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY

hide comments
2020-04-06 09:01:49
multi edge graph.
2017-03-18 20:14:07
@shivucoder55, The car can only be used once from source to destination
2016-03-10 13:40:51
From Source to destination , only 1 time car can be used or we can use more than once but between each pair of cities connected via given roads only 1 time car can be used ? .... Thanks for help in advance
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.