Detail of message

Online Judge

Problem Set

Authors

Online Contests

User

Web Board
Home Page
F.A.Qs
Statistical Charts

Current Contest
Past Contests
Scheduled Contests
Award Contest

哪位大神可以告诉我，这两份代码有什么不同？

Posted by fanjianjin at 2011-03-16 12:54:51 on Problem 2137 and last updated at 2011-03-16 12:55:21

---------------------------WA的代码----------------------------------

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;

int loc[102][42][2];
double dp[42][102][42];

double calc(int x1,int y1,int x2,int y2)
{
	return sqrt((double) ((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)));
}

int main()
{
	int n;
	while (scanf("%d",&n)>0)
	{
		for (int i=1;i<=n;i++) 
		{
			scanf("%d",&loc[i][0][0]);
			for (int j=1;j<=loc[i][0][0];j++)
				scanf("%d%d",&loc[i][j][0],&loc[i][j][1]);
		}
		memset(dp,0,sizeof(dp));
		for (int i=1;i<=loc[1][0][0];i++)
		{
			for (int j=2;j<n;j++)
			{
				for (int k=1;k<=loc[j][0][0];k++)
				{
					double mini=dp[i][j-1][1]+calc(loc[j-1][1][0],loc[j-1][1][1],loc[j][k][0],loc[j][k][1]);
					for (int l=2;l<=loc[j-1][0][0];l++)
						if (dp[i][j-1][l]+calc(loc[j-1][l][0],loc[j-1][l][1],loc[j][k][0],loc[j][k][1])<mini)
							mini=dp[i][j-1][l]+calc(loc[j-1][l][0],loc[j-1][l][1],loc[j][k][0],loc[j][k][1]);
					dp[i][j][k]=mini;
				}
			}
			for (int k=1;k<=loc[n][0][0];k++)
			{
				double mini=dp[i][n-1][1]+calc(loc[n-1][1][0],loc[n-1][1][1],loc[n][k][0],loc[n][k][1])+
						calc(loc[n][k][0],loc[n][k][1],loc[1][i][0],loc[1][i][1]);
				for (int l=2;l<=loc[n-1][0][0];l++)
					if (dp[i][n-1][l]+calc(loc[n-1][l][0],loc[n-1][l][1],loc[n][k][0],loc[n][k][1])+
						calc(loc[n][k][0],loc[n][k][1],loc[1][i][0],loc[1][i][1])<mini)
							mini=dp[i][n-1][l]+calc(loc[n-1][l][0],loc[n-1][l][1],loc[n][k][0],loc[n][k][1])+
						calc(loc[n][k][0],loc[n][k][1],loc[1][i][0],loc[1][i][1]);
				dp[i][n][k]=mini;
			}
		}
		double mint=0x7FFFFFFF;
		for (int i=1;i<=loc[1][0][0];i++)
			for (int j=1;j<=loc[n][0][0];j++)
				if (dp[i][n][j]<mint) mint=dp[i][n][j];
		mint*=100;
		int mina=(int)mint;
		printf("%d\n",mina);
	}
}

----------------------------AC的代码--------------------------------

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;

int loc[102][42][2];
double dp[42][102][42];

double calc(int x1,int y1,int x2,int y2)
{
	return sqrt((double) ((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)));
}

int main()
{
	int n;
	while (scanf("%d",&n)>0)
	{
		for (int i=1;i<=n;i++) 
		{
			scanf("%d",&loc[i][0][0]);
			for (int j=1;j<=loc[i][0][0];j++)
				scanf("%d%d",&loc[i][j][0],&loc[i][j][1]);
		}
		memset(dp,0,sizeof(dp));
		for (int i=1;i<=loc[1][0][0];i++)
			for (int j=1;j<=loc[2][0][0];j++)
				dp[i][2][j]=calc(loc[1][i][0],loc[1][i][1],loc[2][j][0],loc[2][j][1]);
		for (int i=1;i<=loc[1][0][0];i++)
		{
			for (int j=3;j<=n;j++)
			{
				for (int k=1;k<=loc[j][0][0];k++)
				{
					double mini=dp[i][j-1][1]+calc(loc[j-1][1][0],loc[j-1][1][1],loc[j][k][0],loc[j][k][1]);
					for (int l=2;l<=loc[j-1][0][0];l++)
						if (dp[i][j-1][l]+calc(loc[j-1][l][0],loc[j-1][l][1],loc[j][k][0],loc[j][k][1])<mini)
							mini=dp[i][j-1][l]+calc(loc[j-1][l][0],loc[j-1][l][1],loc[j][k][0],loc[j][k][1]);
					dp[i][j][k]=mini;
				}
			}
		}
		double mint=0x7FFFFFFF;
		for (int i=1;i<=loc[1][0][0];i++)
			for (int j=1;j<=loc[n][0][0];j++)
				if (dp[i][n][j]+calc(loc[1][i][0],loc[1][i][1],loc[n][j][0],loc[n][j][1])<mint) mint=dp[i][n][j]+calc(loc[1][i][0],loc[1][i][1],loc[n][j][0],loc[n][j][1]);
		mint*=100;
		int mina=(int)mint;
		printf("%d\n",mina);
	}
}
------------------------------------------------------------

Followed by:

Post your reply here:

User ID:
Password:
Title:

Content:

> ---------------------------WA的代码----------------------------------
> 
> #include<cstdio>
> #include<cstdlib>
> #include<cstring>
> #include<cmath>
> #include<algorithm>
> using namespace std;
> 
> int loc[102][42][2];
> double dp[42][102][42];
> 
> double calc(int x1,int y1,int x2,int y2)
> {
> 	return sqrt((double) ((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)));
> }
> 
> int main()
> {
> 	int n;
> 	while (scanf("%d",&n)>0)
> 	{
> 		for (int i=1;i<=n;i++) 
> 		{
> 			scanf("%d",&loc[i][0][0]);
> 			for (int j=1;j<=loc[i][0][0];j++)
> 				scanf("%d%d",&loc[i][j][0],&loc[i][j][1]);
> 		}
> 		memset(dp,0,sizeof(dp));
> 		for (int i=1;i<=loc[1][0][0];i++)
> 		{
> 			for (int j=2;j<n;j++)
> 			{
> 				for (int k=1;k<=loc[j][0][0];k++)
> 				{
> 					double mini=dp[i][j-1][1]+calc(loc[j-1][1][0],loc[j-1][1][1],loc[j][k][0],loc[j][k][1]);
> 					for (int l=2;l<=loc[j-1][0][0];l++)
> 						if (dp[i][j-1][l]+calc(loc[j-1][l][0],loc[j-1][l][1],loc[j][k][0],loc[j][k][1])<mini)
> 							mini=dp[i][j-1][l]+calc(loc[j-1][l][0],loc[j-1][l][1],loc[j][k][0],loc[j][k][1]);
> 					dp[i][j][k]=mini;
> 				}
> 			}
> 			for (int k=1;k<=loc[n][0][0];k++)
> 			{
> 				double mini=dp[i][n-1][1]+calc(loc[n-1][1][0],loc[n-1][1][1],loc[n][k][0],loc[n][k][1])+
> 						calc(loc[n][k][0],loc[n][k][1],loc[1][i][0],loc[1][i][1]);
> 				for (int l=2;l<=loc[n-1][0][0];l++)
> 					if (dp[i][n-1][l]+calc(loc[n-1][l][0],loc[n-1][l][1],loc[n][k][0],loc[n][k][1])+
> 						calc(loc[n][k][0],loc[n][k][1],loc[1][i][0],loc[1][i][1])<mini)
> 							mini=dp[i][n-1][l]+calc(loc[n-1][l][0],loc[n-1][l][1],loc[n][k][0],loc[n][k][1])+
> 						calc(loc[n][k][0],loc[n][k][1],loc[1][i][0],loc[1][i][1]);
> 				dp[i][n][k]=mini;
> 			}
> 		}
> 		double mint=0x7FFFFFFF;
> 		for (int i=1;i<=loc[1][0][0];i++)
> 			for (int j=1;j<=loc[n][0][0];j++)
> 				if (dp[i][n][j]<mint) mint=dp[i][n][j];
> 		mint*=100;
> 		int mina=(int)mint;
> 		printf("%d\n",mina);
> 	}
> }
> 
> ----------------------------AC的代码--------------------------------
> 
> #include<cstdio>
> #include<cstdlib>
> #include<cstring>
> #include<cmath>
> #include<algorithm>
> using namespace std;
> 
> int loc[102][42][2];
> double dp[42][102][42];
> 
> double calc(int x1,int y1,int x2,int y2)
> {
> 	return sqrt((double) ((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)));
> }
> 
> int main()
> {
> 	int n;
> 	while (scanf("%d",&n)>0)
> 	{
> 		for (int i=1;i<=n;i++) 
> 		{
> 			scanf("%d",&loc[i][0][0]);
> 			for (int j=1;j<=loc[i][0][0];j++)
> 				scanf("%d%d",&loc[i][j][0],&loc[i][j][1]);
> 		}
> 		memset(dp,0,sizeof(dp));
> 		for (int i=1;i<=loc[1][0][0];i++)
> 			for (int j=1;j<=loc[2][0][0];j++)
> 				dp[i][2][j]=calc(loc[1][i][0],loc[1][i][1],loc[2][j][0],loc[2][j][1]);
> 		for (int i=1;i<=loc[1][0][0];i++)
> 		{
> 			for (int j=3;j<=n;j++)
> 			{
> 				for (int k=1;k<=loc[j][0][0];k++)
> 				{
> 					double mini=dp[i][j-1][1]+calc(loc[j-1][1][0],loc[j-1][1][1],loc[j][k][0],loc[j][k][1]);
> 					for (int l=2;l<=loc[j-1][0][0];l++)
> 						if (dp[i][j-1][l]+calc(loc[j-1][l][0],loc[j-1][l][1],loc[j][k][0],loc[j][k][1])<mini)
> 							mini=dp[i][j-1][l]+calc(loc[j-1][l][0],loc[j-1][l][1],loc[j][k][0],loc[j][k][1]);
> 					dp[i][j][k]=mini;
> 				}
> 			}
> 		}
> 		double mint=0x7FFFFFFF;
> 		for (int i=1;i<=loc[1][0][0];i++)
> 			for (int j=1;j<=loc[n][0][0];j++)
> 				if (dp[i][n][j]+calc(loc[1][i][0],loc[1][i][1],loc[n][j][0],loc[n][j][1])<mint) mint=dp[i][n][j]+calc(loc[1][i][0],loc[1][i][1],loc[n][j][0],loc[n][j][1]);
> 		mint*=100;
> 		int mina=(int)mint;
> 		printf("%d\n",mina);
> 	}
> }
> ------------------------------------------------------------

Home Page Go Back To top