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

Post Reply
Solaris
Learning poster
Posts: 99
Joined: Sun Apr 06, 2003 5:53 am
Location: Dhaka, Bangladesh
Contact:

10724 - Road Construction

Post by Solaris » Wed Sep 07, 2005 12:25 pm

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
Location: Dhaka, Bangladesh
Contact:

Post by Solaris » Thu Nov 10, 2005 7:12 pm

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;
}

Where's the "Any" key?

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

10724 help!!!

Post by mysword » Tue Feb 07, 2006 1:28 pm

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

Post by mysword » Wed Feb 08, 2006 5:04 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:

Post by mf » Wed Feb 08, 2006 9:30 am

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

Post by empo » Thu Dec 11, 2008 9:00 pm

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";
	}
}
"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

Post by mf » Thu Dec 11, 2008 10:22 pm

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

Post by mehdiii » Sat Jul 20, 2013 5:40 am

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

Post Reply

Return to “Volume 107 (10700-10799)”