Week 4 Programming Assignment Solution

Select your language (C/C++/Java/Python2/Python3)

Paste your code into the submission window.

There are some public test cases and some (hidden) private test cases.

"Compile and run" will evaluate your submission against the public test

cases.

"Submit" will evaluate your submission against the hidden private test

cases and report a score on 100. There are 20 private testcases in all,

each with equal weightage. You will only get a score on 100. You will not

get feedback on which private testcases passed or failed.

Ignore warnings about "Presentation errors".

Padayatra

(IOI Training Camp, Bangalore, 2004)

The exit polls indicate that the sitting MLA is likely to lose the upcoming

election. The party high command instructs him to undertake a padayatra

through his constituency to boost his popularity. To maximize coverage of the

constituency, the party decides that he should choose a circular route that

returns to the starting point without using any road twice. The route need not

visit all the towns and villages in the constituency.

Being averse to physical exercise, the MLA would like to minimize the

distance that he has to walk. He has a helicopter at his disposal, so he can

begin the padayatra at any town or village.




The task is to help him find the shortest circular route. You are guaranteed

that there is always at least one circular route.




Solution Hint

Given an edge (i,j) with weight W(i,j), the shortest cycle from i to i via j can be

found by temporarily deleting the edge (i,j), finding the shortest path from j to i,

and then adding W(i,j) to the length of this path. Do this systematically to find

the shortest cycle in the graph.




Input format

The first line of input is an integer N, 1 ≤ N ≤ 1000, the number of roads in the constituency. The constituency has no more than 300 towns and villages connected by roads.The next N lines specify the roads. Each line consists of three space separated integers S, T and D where S is the starting point of the road, T is the ending point and D is the length of the road. Each road is a two-way road and is listed exactly once, in one of the two directions.




Output format




A single line with the integer distance around the shortest possible circular

route.




Test data




There are at most 300 towns and villages and at most 1000 roads.

Example

Sample Input

4

3

1

3

1

1

2

2

5

5

4

3

44

Sample output 1

12

Select the Language for this assignment. C++

1 // c++ program to find uhortest weighted

2 // cycle in undirected graph

3 #include <iostream

4 #include <list

5 #include <set

6 #include <vector

7 #include <climits

8 #include <algorithm

9

10 using namespace std;

11

12 struct Edge

13 {

14

int u;

15

int v;

16

int w;

17

Edge(int _u, int _v, int _w) : u(_u), v(_v), w(_w){}

18 };

19

20 // weighted undirected Graph

21 class Graph

22 {

23

int V ;

24

vector< vector< pair<int, int adjList;//first element

25

You may submit any number of times before the due date. The final submission

will be considered for grading.

Assignment will be evaluated only after submitting using Submit button below.

If you only save as or compile and run the Program, your assignment will not be