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
