## 10724 - Road Construction

All about problems in Volume 107. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Solaris
Learning poster
Posts: 99
Joined: Sun Apr 06, 2003 5:53 am
Contact:

### 10724 - Road Construction

I am getting WA in this problem
Cuv = Sum (PreCostij -CurCostij) where CurCostij is the shortest cost path from i to j if the road between (u, v) exists. And PreCostij is the shortest cost route before constructing the road between u and v.
As we are dealing with undirected graph, can i and j change place ??
e.g. Will both PreCost(1,2) and PreCost(2,1) both be considered while calculating the sum ???

And is there any tricky input for this problem?? Please somebody help me with some sample I/O s.

My algo works as follows:
- Floyd-Warshall to get the shortest path
- Select an edge/road for construction (if it was not initially given)
- Update the total cost for the graph, for adding the current road using an O(n^2) loop
- Show the best road (IF REQUIRED)
Where's the "Any" key?

Solaris
Learning poster
Posts: 99
Joined: Sun Apr 06, 2003 5:53 am
Contact:
Still no reply ???

I am posting my code .. will anyone be kind enough to check this code for some inputs. Either I dont understand the problem clearly or I am failing in some tricky cases ...

Code: Select all

``````//PROBLEM NO	: 10724
//PROBLEM NAME	: Road Construction
//DATE			: 06 / 09 / 05

#include <stdio.h>
#include <string.h>
#include <math.h>

#define min(a,b) a<b ? a : b

const int max = 55;

const double eps = 1e-10;
const double inf = 1e15;

double init[max][max];
double prev[max][max];
double curr[max][max];

struct point
{
double x;
double y;
} pnt[max];

int nNode;
int nEdge;

double euler(int i, int j)
{
double x = pnt[i].x - pnt[j].x, y = pnt[i].y - pnt[j].y;
return sqrt(x*x + y*y);
}

/*
int equals(double a, double b)
{
if(fabs(a-b) < eps)
return 1;
return 0;
}
*/

int main(void)
{
int i, j;
int frm, mid, to;

double newCost, prevCost, edgeCost;
double prevSum, currSum;
double diff;

double minSum, minEdge;
int u, v;

#ifndef ONLINE_JUDGE
freopen("c:/programs/input/10724.txt", "r", stdin);
#endif

while(scanf("%d %d", &nNode, &nEdge) == 2)
{
if(nNode==0 && nEdge == 0)
break;

memset(init, 0, sizeof(init));

for(i=1; i<=nNode; i++)
scanf("%lf %lf", &pnt[i].x, &pnt[i].y);

for(i=0; i<nEdge; i++)
{
scanf("%d %d", &frm, &to);

init[frm][to] = init[to][frm] = euler(frm, to);
}

memcpy(prev, init, sizeof(prev));

for(mid=1; mid<=nNode; mid++)
{
for(frm=1; frm<=nNode; frm++)
{
for(to=frm+1; to<=nNode; to++)
{
if(prev[frm][mid] && prev[mid][to] && frm != to)
{
prevCost = prev[frm][to];
newCost = prev[frm][mid] + prev[mid][to];

if(!prevCost || prevCost > newCost)
prev[frm][to] = newCost;
}
}
}
}

prevSum = 0.0;
for(frm=1; frm<=nNode; frm++)
{
for(to=frm+1; to<frm; to++)
{
prev[frm][to] = prev[to][frm];
prevSum += prev[frm][to];
}
}

minSum = inf;
for(frm=1; frm<=nNode; frm++)
{
for(to=frm+1; to<=nNode; to++)
{
if(!init[frm][to])
{
edgeCost = euler(frm, to);
currSum = prevSum;

for(i=1; i<=nNode; i++)
{
for(j=i+1; j<=nNode; j++)
{
//newCost = min((prev[i][frm] + edgeCost + prev[to][j]), (prev[i][to] + edgeCost + prev[frm][j]));
newCost = prev[i][frm] + edgeCost + prev[to][j];

if(newCost < prev[i][j])
{
diff = prev[i][j] - newCost;
currSum -= diff;
}
}
}

if(currSum < minSum)
{
minSum = currSum;
minEdge = edgeCost;

u = frm;
v = to;
}

//if(equals(currSum, minSum) && edgeCost < minEdge)

if(currSum == minSum && edgeCost < minEdge)
{
minEdge = edgeCost;

u = frm;
v = to;
}
}
}
}

minSum += (1.0 + eps);

//if(equals(minSum, prevSum) || minSum > prevSum)
if(minSum >= prevSum)
else
printf("%d %d\n", u, v);
}

return 0;
}

``````
Where's the "Any" key?

mysword
New poster
Posts: 26
Joined: Sun Mar 06, 2005 8:52 am

### 10724 help!!!

can anyone give some sample I/O?
I think my algo is correct but don't know why WA....

mysword
New poster
Posts: 26
Joined: Sun Mar 06, 2005 8:52 am
The problem description says: "If again draw occurs then node pair whose indices are small will be the answer." But as there are a pair of indices (u,v) in the output, how to compare the two indices? Does it mean that first compare u, if u is equal, then compare v ??? do (u,v) and (v,u) both acceptable?

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
http://www.algorithmist.com/index.php/UVa_10724 has an accurate interpretation of the problem statement.
But as there are a pair of indices (u,v) in the output, how to compare the two indices?
Output lexicographically smallest pair. That is, the pair with the smallest value of u, and (secondly) smallest v.

empo
New poster
Posts: 19
Joined: Mon Jul 28, 2008 7:00 pm
Location: India

### Got frustataed now

Wrong Answer !!!!!!5 times in a row...Here is my code ..check it if anyone get time...If anyone have some input for this problem please post that.....

Code: Select all

``````#include<iostream>
#include<math.h>
#define INF 21474478.0
using namespace std;

int points[53][2];

void Initialize()
{
for(int i=1;i<=no_points;i++)
for(int j=1;j<=no_points;j++)
{
if(i==j)
{
checking[i][j]=0;
}
else
{
checking[i][j]=-1;
}
}
}

double calculate_distance(int m,int n)
{
int a = points[m][0] - points[n][0];
int b = points[m][1] - points[n][1];
return sqrt((a*a) + (b*b));
}

void ReInitialize_traveling()
{
for(int i=1;i<=no_points;i++)
for(int j=1;j<=no_points;j++)
}

void floydwarshall(int n)
{
for (int k=1;k<=n;k++) /* k -> is the intermediate point */
for (int i=1;i<=n;i++) /* start from i */
for (int j=1;j<=n;j++) /* reaching j */
{
}
}

double cost_calculation(int n)
{
double cost = 0.0;
for(int i=1;i<=no_points;i++)
for(int j=i+1;j<=no_points;j++)
{
if(n==2)
cost += traveling[i][j];
else
}
return cost;
}

void show_array(int n)
{
for(int i=1;i<=no_points;i++)
{
for(int j=1;j<=no_points;j++)
{
if(n==1)
else
cout<<" "<<traveling[i][j];
}
cout<<endl;
}
}

double minimum(double a,double b,double c)
{
if(a<=b && a<=c)
return a;
if(b<=a && b<=c)
return b;
else
return c;
}

int main()
{
double dist;
int m,n;
{
Initialize();
for(int i=0;i<no_points;i++)
scanf("%d %d",&points[i+1][0],&points[i+1][1]);
{
scanf("%d %d",&m,&n);
dist = calculate_distance(m,n);
checking[m][n] = 0;
checking[n][m] = 0;
}

double preCost = cost_calculation(1);

int index = 0,ansX,ansY;
for(int u=1;u<=no_points;u++)
{
for(int v=u+1;v<=no_points;v++)
{
if(checking[u][v]==-1)
{
solution[index][0] = u;
solution[index][1] = v;
ReInitialize_traveling();
dist = calculate_distance(u,v);
for(int i=1;i<=no_points;i++)
for(int j=1;j<=no_points;j++)
traveling[i][j] = minimum(traveling[i][j],traveling[i][u]+dist+traveling[v][j],traveling[i][v]+dist+traveling[u][j]);
solution[index][2] = preCost  - cost_calculation(2);

if(solution[index][2] > 1.0)
index++;
}
}
}
if(index>0)
{
int a,b;
double newmin,min = 0,dist_X_Y,newdist;
for(int i=0;i<index;i++)
{
a = solution[i][0];
b = solution[i][1];
newdist = calculate_distance(a,b);
newmin = solution[i][2];
if(min<newmin)
{
min = newmin;
ansX = a;
ansY = b;
dist_X_Y = newdist;
}
else if(min==newmin && newdist<dist_X_Y)
{
dist_X_Y=newdist;
ansX = a;
ansY = b;

}
else if(min==newmin && newdist==dist_X_Y && a<ansX)
{
ansX = a;
ansY = b;
}
else if(min==newmin && newdist==dist_X_Y && a==ansX && b<ansY)
{
ansY = b;
}
}
cout<<ansX<<" "<<ansY<<endl;
}
else
}
}
``````
"Accepted" is my passion but RTE is my weakness.....

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

### Re: 10724 - Road Construction

Floating-point operations aren't exact, you should always use epsilons when comparing floats.

mehdiii
New poster
Posts: 9
Joined: Fri Nov 02, 2012 1:35 pm

### Re: 10724 - Road Construction

Some Correct input and output :

Input :

Code: Select all

``````10 20
23 62 15 28 72 83 56 80 30 30 98 82 51 76 39 21 65 83 72 9
1 2 1 3 2 4 2 5 4 6 4 7 6 8 3 9 7 10
7 5
4 9
1 2
10 2
9 8
6 9
6 5
9 7
1 4
8 2
8 6

10 20
41 40 10 85 9 57 37 43 17 92 55 32 47 21 69 44 87 23 8 78
1 2 2 3 3 4 1 5 3 6 5 7 4 8 3 9 4 10
8 1
6 4
8 9
2 4
8 3
9 3
4 5
2 10
4 9
3 7
3 1

10 20
44 68 75 59 12 41 78 56 18 52 72 64 61 1 27 3 74 48 66 40
1 2 2 3 2 4 2 5 3 6 3 7 7 8 3 9 6 10
4 9
8 5
5 6
2 9
4 3
7 9
5 1
4 1
7 6
7 6
9 3

20 50
9 65 81 99 96 64 40 77 0 79 81 72 49 91 29 42 2 86 23 96 33 34 53 97 43 17 73 5 86 62 39 97 44 99 76 39 34 16 94 0
1 2 2 3 1 4 1 5 2 6 4 7 7 8 6 9 7 10 7 11 2 12 9 13 8 14 13 15 6 16 4 17 7 18 4 19 9 20
13 6
12 7
4 2
13 11
10 1
10 16
14 13
2 12
10 20
2 18
16 19
19 17
5 20
6 17
9 10
13 20
9 19
1 6
18 9
16 5
15 16
7 6
12 11
3 15
7 8
20 19
11 1
16 11
12 13
3 19
19 13
0 0
``````
Output :

Code: Select all

``````5 8
4 7
2 6
8 11
``````