作者Dick901 (Sword)
看板ACMCLUB
标题[问题] uva 116 Unidirectional TSP 找不出错误
时间Wed Oct 13 21:33:41 2010
这一题，我在uva上judge都是wrong answer，但是在zerojudge上却是accept answer，
我知道zerojudge的测资比较弱，但是我用了网路上Mat大大给的测资试，没有问题啊！
可否请大大们帮我看看有没有哪里有bug！谢谢！
my code:
===========================================================
#include <stdio.h>
int M[20][110];
int dp[20][110];
int pa[20][110];
int main()
{
int m,n,i,j,k,min,thr[3];//thr阵列用来判断上中下，请见下一个注释
while(scanf("%d%d",&m,&n)!=EOF)
{
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
scanf("%d",&M[i][j]);
}
}
for(i=0;i<m;i++)
dp[i][n-1]=M[i][n-1];
for(i=n-2;i>=0;i--)
{
for(j=0;j<m;j++)
{
if(j==0) //这个if用来判断前一行与他相邻的三个dp
{ //阵列元素的上下位置，因为题目要求按照字典序，
thr[0]=j; //我的方法比较笨，请各位谅解！
thr[1]=j+1;
thr[2]=(j-1+m)%m;
}else if(j==m-1){
thr[0]=(j+1+m)%m;
thr[1]=j-1;
thr[2]=j;
}else{
thr[0]=j-1;
thr[1]=j;
thr[2]=j+1;
}
min=dp[thr[0]][i+1];
pa[j][i]=thr[0];
for(k=1;k<3;k++)
{
if(min>dp[thr[k]][i+1])
{
min=dp[thr[k]][i+1];
pa[j][i]=thr[k];
}
}
dp[j][i]=min+M[j][i];
}
}
min=dp[0][0];
int ps=0;
for(i=1;i<m;i++)
{
if(min > dp[i][0])
{
min=dp[i][0];
ps=i;
}
}
for(i=0;i<n-1;i++)
{
printf("%d ",ps+1);
ps=pa[ps][i];
}
printf("%d\n",ps+1);
printf("%d\n",min);
}
return 0;
}
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 210.60.107.236