10724 - Road Construction

[Solaris]

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)

[Solaris]

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)
			printf("No road required\n");
		else
			printf("%d %d\n", u, v);			
	}
	
	return 0;
}

[mysword]

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

[mysword]

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]

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]

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;

double  links[53][53],checking[53][53],traveling[53][53],solution[1225][3];
int points[53][2];
int no_points,no_links;

void Initialize()
{
	for(int i=1;i<=no_points;i++)
		for(int j=1;j<=no_points;j++)
	{
		if(i==j)
		{
			links[i][j] = 0;
			checking[i][j]=0;
		}
		else
		{
			links[i][j] = INF;
			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++)
			traveling[i][j] = links[i][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 */
				if (links[i][k] + links[k][j] < links[i][j])
	{
		links[i][j] = links[i][k]+links[k][j];
		links[j][i] = links[i][k]+links[k][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
			cost += links[i][j];
	}
	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)
				cout<<" "<<links[i][j];
			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;
	while(scanf("%d %d\n",&no_points,&no_links) && (no_points || no_links))
	{
		Initialize();
		for(int i=0;i<no_points;i++)
			scanf("%d %d",&points[i+1][0],&points[i+1][1]);
		for(int i=0;i<no_links;i++)
		{
			scanf("%d %d",&m,&n);
			dist = calculate_distance(m,n);
			links[m][n] = dist;
			links[n][m] = dist;
			checking[m][n] = 0;
			checking[n][m] = 0;
		}

		floydwarshall(no_points);//on links matrices
		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
			cout<<"No road required\n";
	}
}

[mf]

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

[mehdiii]

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