SP26349 NINJA6 - TRAVELLING DILEMMA

**Problem statement:** A graph of a country is given. There are N cities and M number of roads. Each road connect 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 maynot 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. **Constraints:** 1 2 1 1 1 **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. **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 **Sample output:** 8

N/A

N/A